An approach better than Pancake Sorting for a restricted sort
The original source of the question for this blog post is again Algo Geeks. Here's the problem description: There is an array in an external system which cannot be accessed directly. The system exposes 3 functions whose complexity is O(1) : length() - returns the length of the array. get(i) - returns the element at index i. reverse(i,j) - reverses the elements in the array from index i to index j (both indexes inclusive). Sort the array in the best possible way using only these 3 operations? The direct solution to sorting in this case is a Pancake Sort (see the video embedded below). Pancake sort has a direct implementation complexity of O(N2) as locating the max element in the unsorted section of the array is an O(N) operation. Besides this, i t is obvious that one cannot use standard quicksort or heapsort directly since a swap operation isn't supplied. However, we can simulate a swap operation using the reverse operator. It's easy to do:...