Sorting by repeated reversal
If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j &lt; i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices to show that the inner while loop terminates when $i = 1$.
Suppose that the inner while loop never terminates when $i = 1$. Let $j$ be the maximal value which appears infinitely many times as $A[1]$. After finitely many iterations, $A[1] \leq j$ always. Since $A[1] = j$ infinitely many times, there must be some subsequent iteration in which $A[1] = j$. After that iteration, $A[j] = j$. In all subsequent iterations, $A[1] \leq j$, which ensures that $A[j]$ stays $j$, guaranteeing that $A[1]$ never equals $j$ again. However, this contradicts the definition of $j$.
The maximal number of iterations of the inner loop is A000375. There is no known formula!
I couldn't find the sequence for the maximal total number of iterations of the inner loop (over all $i$) on OEIS.