Runtime for Terrible "Sorting Algorithm"? Before I begin, I apologize for the bad wording. Consider the following "sorting algorithm":
Suppose there are $n$ books on the bookshelf labeled $1$-$n$, and ordered from left to right in a random way. Your goal is to end up with a sorted bookshelf from left to right with $1$ at the left and $n$ at the right. The algorithm is as follows:

*

*Pick a book at random that's not already in its correct position, say book $r$.

*Remove the book from its current position and place it at its correct position (position $r$)

*In the process, slide the books in between the original incorrect position of book $r$ and position $r$ towards the gap left open.

*Repeat if it's not sorted already, and if it is sorted, the algorithm terminates.

For example, suppose $n = 5$ and our original permutation is $5, 4, 3, 2, 1$ and suppose $r = 2$. Then after one step of the algorithm, the permutation becomes $5, 2, 4, 3, 1$.
Prove that regardless of the choice of the random book at each step of the algorithm that the algorithm will eventually terminate.
What is the worst case runtime of this algorithm? (I believe it occurs with $2, \dots, n, 1$ with $r$ being the left most book at each step and runtime roughly $2^{n - 2}$).
 A: Here is a quote of my 2009 proof @ AoPS that the algorithm will eventually terminate:
For a permutation $ p$, consider a function $ f(p) := \sum_{j=1}^n |p_j - j|$, i.e., the sum of absolute differences of elements and their positions in $ p$.
In the sorting process this function never increases but occasionally can decrease. It is clear that $ f(p)\geq 0$ and $ f(p) = 0$ only if the permutation $ p$ is sorted.
In an infinite sorting this function must take a constant non-zero value after some step.
Suppose that there exists an infinite sorting process and let $ n$ be the smallest possible integer that admits such an infinite sorting.
Let $ x$ be the smallest elements that jumps infinite number of times. Then after some step in the sorting process no element smaller than $ x$ jumps at all and the function $ f(p)$ does not decrease. Without loss of generality assume that this happens straight from the beginning of the sorting process (simply by ignoring everything what happened before).
Since $ x$ jumps infinite number of times, it takes its correct place in the permutation an infinite number of times. However, it can leave its correct place only if there exists an element larger than $ x$ somewhere before $ x$ (whose jump would shift $ x$ from its correct place). Therefore, there exists an element $ y$ smaller than $ x$ somewhere after $ x$.
Since $ y < x$, it never jumps itself and can be shifted by jumps of other elements only towards the end of the permutation (as otherwise $ f(p)$ would decrease). But this way it cannot be shifted infinitely many times, so after some point $ y$ takes a fixed place in the permutation.
As soon as that happened, the sorting can be considered as two independent sortings -- at the left hand side of $ y$ and at the right hand side of $ y$ since no element jumps across $ y$ from one "half" to the other. Moreover, sorting of the left "half" must be infinite as it contains $ x$. Renaming the elements at the left hand side of $ y$ will give a permutation on smaller number of elements that admits an infinite sorting, a contradiction to the minimality of $ n$.
This contradiction proves that no infinite sorting is possible.

Another approach:
Alternatively, we can take $ y = 1$ right away (without considering any $x$) and notice that if it ever takes its correct place then we have an infinite sortings of the remaining $n-1$ elements, a contradiction to the minimality of $ n$. Otherwise, $ y$ will be shifted towards the end of the permutation and sooner or later will take a fixed position, again splitting the permutation into two smaller ones, at least one of which will be subject to infinite sorting in contradiction to the minimality of $n$.

PS. It is conjectured that $2^{n-1}-1$ is the tight upper bound for the number of steps (attained at permutation $(n,1,2,\dots,n-1)$, for example), but to best of my knowledge it was not proved.
