# Sorting by repeated reversal

Let $$A$$ be an array of $$n$$ integers containing the numbers $$\{1, 2, \dots , n\}$$ in some arbitrary order. For integers $$i$$ and $$j$$ such that $$1 ≤ i < j ≤ n$$, let $$\mathrm{Reverse}(A, i, j)$$ be a procedure that reverses the subarray $$A[i], A[i + 1], \dots , A[j]$$ of the array $$A$$ while leaving the remaining elements of the array unaffected. Prove that the following algorithm sorts the array $$A$$ and also terminates.

for i := 1 to n − 1
while A[i] ≠ i do
Reverse(A, i, A[i])

I am able to prove this if the elements are in descending order. Why does this algorithm work for an arbitrary order?

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 < 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.

• Its a good answer, but I think you will need to explain more why $j$ will stay at its place. We can prove (by induction on the time $t$ after we saw $j$ for the first time) that for any $A[1]=k$ which came after the iteration for which $A[1]=j$, we have $k<j$ (and not only $k\le j$). This is followed by that $j$ is maximal and is unique (there is only one $j$ in the array). – nir shahar May 4 at 20:39
• It's a simple induction. – Yuval Filmus May 4 at 20:40
• Can u please explain it with an example like taking a small array e.g [9,3,1,8]?? – Danjing_Chaw May 5 at 11:36
• Your example is not a permutation of $1,\ldots,n$. Also, you can work out any specific example by hand, or by programming the algorithm. – Yuval Filmus May 5 at 12:02
• Okay got it!. It is clear now. – Danjing_Chaw May 5 at 14:42

If you're familiar with cycle sort, you can start to see that this algorithm also operates in a similar way (although it's super inefficient).

Essentially, the inner loop doesn't terminate until the element in the current position $$i$$ is $$i$$. So when the outer loop moves on to the next element, you are guaranteed that the subarray to the left is sorted and in the final state ($$1,2,3,\dots,i-1$$)

Now to prove that the inner loop terminates... assume that it never terminates. So at a certain point, the value at $$A[i]$$ will loop through some values $$t_1,t_2,\dots,t_k$$, none of which are $$i$$. Let $$T=\{\text{all values A[i] loops through infinitely}\}$$. Clearly $$|T|.

When $$t_2$$ is at $$i$$, then $$t_1$$ will be at position $$t_1$$. For $$t_1$$ to ever return to position $$i$$ (which it must as it's an infinite loop), there must be a $$t_p>t_1$$ in $$T$$. Otherwise $$A[t_1]$$ will never be affected by a reversal.

By symmetry this is true of all $$t_j \in T$$. Hence $$T$$ must contain an element which is strictly larger than every element in $$T$$... a contradiction. Hence the inner loop terminates.

You could also say that this finite set $$T$$ must contain an infinite sequence of strictly increasing numbers, which is not possible.

• @Yuval Filmus Thanks for the edits – Hannah W. May 5 at 10:08