mjhjmtu

Making a standard bureocracy (using Word tables), I arrived to the following

Problem. Assume that we have a table with $n+1$ rows. The first $n$ rows are filled with names of students (and say topics of their Master works) and the last row is empty. It is required to sort this table in alphabetic order (of student names) using the operations of cut and copy-past over rows. What is the complexity of this problem (i.e., the smallest number of cut-copy-past operations in the worst case)?

I suspect that this problem has been considered (say in Computer Sciences) but I can not find a proper reference.

Remark. A simple argument shows that this worst case complexity is between $n$ and $frac32n$ (more precisely, $lfloorfrac32nrfloor+1$).

Can we always do better than $frac32n$?

No, $frac32n$ is optimal. Consider the case in which the initial order has the elements swapped in pairs, $BADCFEHG...$. Take any possible sequence of moves that sorts them; we shall show that this sequence contains at least $frac32n$ moves.

Focus on the first two locations 1 and 2 (those that contain $BA$ initially). We associate to them three distinct operations among the ones in the sequence:

• the first operation that involves one of the first two elements (locations 1-2 in the list), which will swap one of the initial elements appearing in it with the empty space;


• the operation that writes $A$ in location 1 (for the last time, if there is more than one);


• the operation that writes $B$ in location 2 (for the last time, if there is more than one).

Note that these are three distinct operations, and they all involve cutting-and-pasting either the letter $A$ or the letter $B$.

Similarly, we can associate three distinct operations of the sequence to each pair of consecutive locations $(2i-1,2i)$: the first one that involves either location $2i-1$ or $2i$, the last one that involves location $2i-1$, and the last one that involves location $2i$. All of these involve cutting-and-pasting one of the two letters that go in those locations, hence there cannot be duplicates with the ones associated to a different pair.

We have built a list of $frac32n$ distinct operations among those in the sequence, so this proves that the sequence has length at least $frac32n$.

For completeness: the $frac32n$ optimal algorithm is: we have to apply a certain permutation of the letters; decompose this permutation into disjoint cycles; each $k$-cycle permutation can be applied in $k+1$ distinct operations using the empty location $X$; for instance $$BCDAXto BCDXA to BCXDA to BXCDA to XBCDA to ABCDX$$
I hope the general strategy is clear to see from this example: swap $X$ with the preceding letter $k$ times, then move back $A$ into place.