How to sort a permutation by reversing subsequences (taken from Skiena 3rd ed.)

Question

I've been stuck on the second part of the following question from Skiena (The Algorithm Design Manual, 3rd ed.) for the past 24 hours and it's driving me nuts! I'm struggling to come up with new ideas at this point, and would appreciate some tips/solutions.

Exercise 4-27 Suppose you are given a permutation p of the integers 1 to n, and seek to sort them to be in increasing order [1, . . . , n]. The only operation at your disposal is reverse(p,i,j), which reverses the elements of a subsequence (p_i, ..., p_j) in the permutation. For the permutation [1, 4, 3, 2, 5] one reversal (of the second through fourth elements) suffices to sort.

• Show that it is possible to sort any permutation using O(n) reversals.
• Now suppose that the cost of reverse(p,i,j) is equal to its length, the number of elements in the range, |j − i| + 1. Design an algorithm that sorts p in O(nlog^2n) cost.

The first part appears fairly straightforward if we brute-force it: locate the position of the largest/smallest value and reverse the subsequence that will place it in the correct position. Repeat for the next largest/smallest value until the sequence is in the correct order. Clearly this requires n reversals at most.

But if I apply this brute-force approach to the second part of the question, it seems like the cost could be O(n^2) in the worst-case scenario. Anyone got any suggestions?

Answer 1

There is an algorithm for in-place merge sort that fits:

1. Sort the beginning half of the array;
2. Sort the last half of the array;
3. Merge the two halves in-place.

The merge takes O(N log N) time:

1. Determine the number of elements in the first half that belong in the second half;
2. Swap those last elements in the first half with the first elements in the second half. You can do this with 3 reversals
3. Recursively merge the 2 pieces in the first and last halves

Since merge takes O(N log N) time, the whole sort takes O(N log² N) time.