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.