Special Sorting

Question

There is an external array of integers on which you can perform the following operations in O(1) time.

1. get(int i) - returns the value at the index 'i' in the external array.
2. reverse( int i, int j) - returns the reverse of the array between index positions i and j (including i and j).

example for reverse: consider an array {1,2,3,4,5}. reverse(0,2) will return {3,2,1,4,5} and reverse(1,4) will return {1,5,4,3,2}.

Write a code to sort the external array. Mention the time and space complexity for your code.

Obviously We can sort in nlogn using quick sort or merge sort. But given the scenerio can we do better?

Answer 1

To sort an array is to find the permutation, or shuffle, that restores it to a sorted state. In other words, your algorithm determines which of the n! possible permutations must be applied, and applies it. Since your algorithm explores the array by asking yes-no questions (Is cell i smaller or greater than cell j?) it follows an implicit decision tree that has depth log(n!) ~ n*log(n).

This means there will be O(n*log(n)) calls to get() to determine how to sort the array.

An interesting variant is to determine the smallest number of calls to reverse() necessary to sort the array, once you know what permutation you need. We know that this number is smaller than n-1, which can be achieved by using selection sort. Can the worst case number be smaller than n-2 ? I must say that I have no idea...

Answer 2

Assuming you want to minimize the number of external operations get and reverse:

• read all integers into an internal array by calling get n times
• do an internal sort (n log in internal ops) and calculate the permutation
• sort the external array by calling reverse a maximum of n times

This has O(n) time and O(n) space complexity.

Edit in response to anonymous downvotes: when talking about time complexity, you always have to state, which operations are to be counted. Here I assumed, only the external operations have a cost.

Answer 3

I'd try to reduce the problem to a classic swaps() based sorting algorithm.

In the following we assume without loss of generality j>=i:
Note that swap(i,j) = reverse(i,j) for each j <= i+2, the reversed sub array is only swapping the edges if there are 3 or less elements
Now, for any j>i+2 - all you need is just reverse() the array, by this swapping the edges - and then reverse the "middle" to get it back to the original, so you get: swap(i,j) = reverse(i,j) ; reverse(i+1,j-1)

Using the just built swap(), you can use any compare based algorithms that uses swaps, such as quicksort, which is O(nlogn). The complexity remains O(nlogn) since for each swap() you need up to 2 reverse() ops, which is O(1)

EDIT: Note: This solution fits for the original question (before it was editted), which asked for a solution, and not to optimize it better then quicksort/mergesort.

Answer 4

Based on get(int i) and reverse( int i, int j), we can't optimise the code. It will have same complexity.