Sorting by insertion of leading elements (Q1096394): Difference between revisions

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.