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.
