Algorithm:Sort using Median and Just 1 comparison in $ O(n \log n) $

Question

I am trying to write an sorting algorithm which takes an input array and produces the sorted array. Following are the constraints for an algorithm.

1. Time complexity = $O(n \log n)$
2. Only one comparison operation throughout the algorithm.
3. We have a function which can provide an median for a set of three elements.

I have tried finding a solution and following is my result.

1. we use the median function to get the smallest and the largest pair. Example: Give an array A[1..n], we get the median of the first three elements, lets call it a set and we receive a $Median$. In next Iteration we remove the received median from the set and add next element to the set and again call Median function. This step when repeated over the length produces a pair of the largest and the smallest element for the entire array.

2. We use this pair, use the comparison operation and place them at position A[0] & A[n-1].

3. We repeat the same operation over the array A[1..n-2] to get another pair of the largest and smallest.

4. We take the median with the A[0] and newly received pair.

5. Median Value is placed at the A[1].
6. We take the median with the A[n-1] and newly received pair.
7. Median Value is placed at the A[n-2].

Step 3~7 are repeated to get a sorted array.

This algorithm satisfies the condition 2 & 3 but not the time complexity. I hope if someone can provide some guidance how to proceed further.

Answer 1

Quicksort (presented in reverse order) works like this. Suppose you have an array:

 [1, 4, 5, 2, 3]

Quicksort in the abstract basically works by sliding towards the middle of the array from both the left and the right side. As we slide inwards, we want to swap items such that big things get moved to the right, and small things get moved to the left. Eventually we should have an array where all the small stuff is on the left, and all the big stuff is on the right.

The upshot of this process also guarantees that one element will be placed in the correct location (because everything to the left of it will be smaller, and everything to the right will be bigger, so it must be in the right position). That value is called the pivot. The first step of quicksort is to ensure the pivot is in the right place.

The way we do this is by selecting a random element to be our pivot - the item we wan to put into it's correct place. For this simple example we'll just use the last number (3). The pivot is our comparison value.

Once we have selected our pivot/comparison value, we then monitor the left-most element (1), and the right-most element (3). We'll call these the left-pointer and the right-pointer. The left-pointers job is to slide towards the middle of the array, stopping when it finds something that is larger than the pivot. The right pointer does the same thing, but it slides inward looking for values less than the pivot. In code:

while (true) {
    while (array[++left] < pivot);
    while (array[--right] > pivot) if (left == right) break;

    if (left >= right) break;           // If the pointers meet then exit the loop
    swap(array[left], array[right]);    // Swap the values otherwise.
}

So in our example above, when the left-pointer hits (4) it recognizes that that is higher than our pivot element and stops moving. The right pivot does the same thing from the right side, but stops when it hits (2) because that's lower than the pivot. When both sides stop, we do a swap, so we end up with:

[1, 2, 5, 4, 3]

Notice that we are getting closer to sorted. We continue to move both pointers inward until they both point to the same element, or they cross - whichever comes first. When that happens, we make one final step, which is to replace the pivot element (3) with whatever point the left/right-pointers are pointing to, which in this case would be (5) because they would both stop right in the middle. Then we swap, so that we get:

[1, 2, 3, 4, 5] 
(Notice that we swap the original pivot (3) with the value pointed to by both sides (5))

This whole process is called a partition. In code it looks like this:

int partition(int *array, int lBound, int rBound) {
    int pivot = array[rBound];          // Use the last element as a pivot
    int left = lBound - 1;              // Point to one before the first element
    int right = rBound;             // Point to the last element;

    // We'll break out of the loop explicity
    while (true) {

        while (array[++left] < pivot);
        while (array[--right] > pivot) if (left == right) break;

        if (left >= right) break;    // If the pointers meet then exit the loop
        swap(array[left], array[right]);    // Swap the pointers otherwise.
    }

    swap(array[left], array[rBound]);   // Move the pivot item into its correct place
    return left;    // The left element is now in the right place
}

It's important to note that although the partition step fully sorted our array in this example, that's not ordinarily the point of the partition step. The point of the paritition step is to put one element into it's correct place, and to ensure that everything left of that element is less and everything to the right is more. Or in other words, to move the pivot value into its correct location and then guarantee that everything left of the pivot is smaller than it, and everything to the right is bigger. So although in this example the array was completely sorted, in general we can only guarantee that one item and one item only is in the correct location (and everything to the left and right is bigger/smaller respectively). This is why the partition method above returns left, because it tells the calling function that this one element is in the correct location (and the array has been correctly partitioned).

That is if we start with an array like:

[1, 7, 5, 4, 2, 9, 3]

Then the partition step would return something like this:

[1, 3, 2, [4], 7, 5, 9]

Where [4] is the only value guaranteed to be in the right place, but everything to the left is smaller than [4] and everything to the right is bigger (though not necessarily sorted!).

The second step is to perform this step recursively. That is, if we can put one element into it's correct location, then we should be able to eventually put all items into their correct location. That is the quicksort function. In code:

int *quicksort(int *array, int lBound, int rBound) {
    if (lBound >= rBound) return array;   // If the array is size 1 or less - return.

    int pivot = partition(array, lBound, rBound);   // Split the array in two. 
    quicksort(array, lBound, pivot - 1);    // Sort the left size. (Recursive)
    quicksort(array, pivot + 1, rBound);    // Sort the right side. (Recursive) 

    return array;
}

Notice that the first step is to ensure that we have an array side of at least 2. It doesn't make sense to process anything smaller than that so we return if that condition isn't met. The next step is to call our partition function which will split the array according to the process outlined above. Once we know that the array has one element that is in correct position, we simply call quicksort again, but this time on the left side of the pivot, and then again on the right side of the pivot. Notice we don't include the pivot because the partition is guaranteed to put that into the correct location!

If we continue to call quicksort recursively, eventually we'll halve the array and partition it until we get arrays of size-one (which by definition is already sorted). So we partition, then halve, partition, halve, etc. until the entire array is sorted (in place). This gives us a sort in O(n lg(n)) time. Cool!

Here's a quick example of it's use:

int main() {
    int array [] {1, 0, 2, 9, 3, 8, 4, 7, 5, 6};

    quicksort(array, 0, 9); // Sort from zero to 9.

    // Display the results
    for (int index = 0; index != 10; ++index) {
        cout << array[index] << endl;
    }

    return 0;
}

A good visual demonstration can be found here: http://www.youtube.com/watch?v=Z5nSXTnD1I4

Answer 2

Steps 1 and 2 are indeed the first steps of a correct solution. Once you know the smallest and largest elements, though, the median oracle is a comparison oracle; if you want to compare a[i] with a[j], then a[i] < a[j] exactly when a[i] = median(a[i], a[j], a[0]) where a[0] is the smallest element. So you can run straight quicksort or mergesort or whathaveyou.