Using your Head is Permitted

Consider a permutation over the numbers 1 through n. For example, with n=7, one can think of the permutation [1, 4, 5, 6, 2, 3, 7].

Let us define a Block Move as a function that makes a new permutation from an existing permutation by taking a contiguous block from it and placing it in a new position. The permutation given above, for example, can be made into the permutation [1, 2, 3, ..., 7] by a single block move. All we need to do is to take the block "4, 5, 6" and move it to be between the "3" and the "7". We say that the original permuation can be sorted in 1 block move.

Not all permutations are this easy to sort. The permutation [4 3 2 1 5 13 12 11 10 9 8 7 6], for example, was shown by help from a computer to require at least 8 block moves to be sorted.

This month's riddle is regarding sorting the inverse permutation [n, n-1, ..., 3, 2, 1]. Answer the following question:

How many block moves does it take to sort the inverse permutation (as a function of n)?

To demonstrate the correctness of your answer, prove that the number you give is a minimum bound and describe an algorithm that sorts in this number of block moves.

List of solvers: