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 pasted into the remaining string, possibly reversed. We give short proofs that every permutation of $[n]$ can be transformed to the identity in at most $\flr{ 2n/3}$ such moves and that some permutations require at least $\flr{ n/2}$ moves.
Categories: math.CO