Short Proofs for Cut-and-Paste Sorting of Permutations

Daniel Cranston, I. Hal Sudborough, Douglas B. West

We consider the problem of determining the maximum number of moves required to sort a permutation of $[n]$ using cut-and-paste operations, in which a segment is cut out and then pa…