An algorithm that sorts in this many moves for odd n is one that takes a block of size 2 from the middle of the segment after the number n and places it in the middle of the segment that is before the number n. When there is nothing left after the n, the remaining permutation is one block move away from a sorted permutation. Here is how it works for n=7:
[7, 6, 5, 4, 3, 2, 1] [4, 3, 7, 6, 5, 2, 1] [4, 5, 2, 3, 7, 6, 1] [4, 5, 6, 1, 2, 3, 7] [1, 2, 3, 4, 5, 6, 7]
For an even n, simply ignore the last element, sort the permutation as though it contains only n-1 elements, then move the n'th element to its correct position using an extra move.
This can be shown to be the minimum number of moves required (again, ignoring the cases n=1 and n=2) by considering the number of places in which an element is smaller than the element that comes after it. For the inverse permutation this statistic is 0 and we want to raise it to n-1 (its value in the identity permutation). In each move, three elements change their following elements (the one before the beginning of the block, at the end of the block, and before the position where the block is to be inserted). This gives a potential for an increase of 3 in our chosen statistic on each move, but, in fact, it is easy to see that no more than an increase of 2 can be achieved in practice.
As a representative case, consider the move from [..., a, b, ..., c, d, ..., e, f, ...] to [..., a, d, ..., e, b, ..., c, f, ...]. For it to increase the statistic by 3, the following inequalities must all hold simultaneously:
a<d<c<f<e<b<a
leading to the impossible a<a.
This, already, gives a bound of ceil((n-1)/2). The reason an extra move is required is that both the first and last moves can increase the statistic by no more than one.
Q.E.D.
As a side note, the permutation cited in the question, for n=13:
[4 3 2 1 5 13 12 11 10 9 8 7 6]
is one of the first permutations to be discovered to require more moves to sort than the inverse permutation. It has, since then, been shown that all odd n from 13 on have such "extra-difficult" permutations. See
H. Eriksson, K. Eriksson, J. Karlander, L. Svensson and J. Wästlund, Sorting a bridge hand, Discrete Math 241:289--300, 2001.
and also theorem 10 of
Isaac Elias, Tzvika Hartman, "A 1.375-Approximation Algorithm for Sorting by Transpositions," IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 3, no. 4, pp. 369-379, Oct-Dec, 2006.
for further details.
This riddle was chosen to be in "Using your Head is Permitted" this month as a tribute to the fact that the "Using your Head is Permitted" main page has now been reorganized so that riddles are shown in the table in the reverse order of their publication (most recent first) as opposed to the order of publication (most recent last), which is how it was arranged previously.
The rearrangement was performed on the HTML source file using the algorithm described in this page.