SwaggyC SwaggyC - 1 month ago 16
Java Question

Going from IntroSort to a MergeSort

I know that when IntroSort is called with something like a T[], say Integer[] x; It will sort the array until the recursive depth is too much (goes to 0, in most implementations), then it will switch to a HeapSort. However, I am trying to call a modified MergeSort when the recursive depth becomes 2log2n. The modified MergeSort only uses a temporary array that is half the size of the original array, just to save a bit of time and space. Anyhow, I have basically copied over all of QuickSort except I added a depth_limit check before it recursively calls.

private void quicksort(T[] items, int left, int right) {
int depth_limit = (int) (2*Math.log(items.length));
if(depth_limit == 0)
{
mergesorter.sort(items, left, right);
return;
}
int pivotindex = findpivot(items, left, right);

// curr will be the final position of the pivot item.
int curr = partition(items, left, right, pivotindex);

if ((curr - left) > 1) {
quicksort(items, left, curr - 1); // Sort left partition
}
if ((right - curr) > 1) {
quicksort(items, curr + 1, right); // Sort right partition
}
}


I would think this would work, since I believe

depth_limit = 2*log2(n) where n is the number of inputs

So my question is, where do I check for recursion depth to switch to MergeSort and am I calculating my depth correctly?

Answer

Depth limit is usually passed as a parameter, with an entry / helper function that calls quicksort() with the initial value for depth limit. Wiki has an example, sort() is the helper function that passes the depth limit to quicksort():

http://en.wikipedia.org/wiki/Introsort

items.length is not going to change. Use (right - left)+1 to get the length of the current sub-array if this is needed.

Note that worst case scenario for quicksort is that a sub-array of length m is split into two sub-arrays, one of length 1, one of length m-1, unless the pivot is excluded, in which case worst case lengths for recursion are 1 and m-2 (the pivot is already in the proper location).

The merge sort would only have to sort the sub array from &T[left] to &T[right].

Either a top down or bottom up merge sort can use a working array 1/2 the size of the original array by sorting both halves of the original array, then copying the first half of the array to the working array, then doing a final merge of the working array and second half of the original array back into the original array (for odd size original array, the working array and "first" half array size is n/2 + 1).