Sorting by insertion of leading elements (Q1096394)

Consider the operation on permutations consisting of removing the leading element and inserting it somewhere in the string. The number of such operations required to sort a permutation \(\sigma\) of \(\{\) 1,...,n\(\}\) into increasing order is n-k, where k is the largest integer such that the last k entries of \(\sigma\) form an increasing sequence. There is a deterministic version of the problem in which the leading element is always inserted into the position equal to its value, and the process ends when 1 reaches the front. The permutation requiring the greatest number of steps to termination is 23...n1, and it requires \(2^{n-1}-1\) steps.