Sorting with reversals II [Solution]

The problem was:

You have an size $n$ array of zeroes, ones and twos. The only write operation is to reverse a sub-array (paying cost equal to the length of the the sub-array). Can we sort the array in $O(n \log n)$ cost?

Solution

---

One solution is to use divide and conquer.

Suppose you divided the array into two approximately equal halves, and sorted each sub-array separately.

Then you will see an array like


$$0 \dots 0 1 \dots 12 \dots 2\vert 0 \dots 0 1 \dots 1 2 \dots 2$$

Now, we can sort a chunk of 2s and 0s by doing a cyclic shift of the chunk $2 \dots 2 0 \dots 0$, so that it looks like $0 \dots 0 2 \dots 2$.

We can do a cyclic shift of an array using only three reversals. Say you want to cyclic shift $a_1, \dots a_m$ to look like $a_k, a_{k+1}, \dots, a_m, a_1, a_2, \dots a_{k-1}$. This we can achieve by first reversing $a_1, \dots a_{k-1}$ and $a_k \dots a_m$, so the array now looks like $a_{k-1}, \dots a_1, a_m, \dots a_{k+1}, a_k$ and then reversing the whole array.

Each reverse costs $O(n)$, and with a constant number of these, give the two sorted halves, we can sort the whole array.

Thus the cost satisfies the recurrence

$$C(n) = 2 C(n/2) + O(n)$$

which gives us $C(n) = O(n \log n)$.