Qucksort gets StackOverflowError for 100000 elements but mergesort does not in Java

Question

According to this SO post:

The common cause for a stack overflow is a bad recursive call.

Then why does it run for 10000 elements but get StackOverflowError for 100000 elements?

Quicksort:

public static void quicksort(int[] data, int low, int high) {
    if (low < high) {
        int p = partition(data, low, high);
        quicksort(data, low, p);
        quicksort(data, p + 1, high);
    }
}
public static int partition(int[] data, int low, int high) {
    int pivot = data[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (data[i] < pivot);
        do {
            j--;
        } while (data[j] > pivot);
        if (i >= j)
            return j;
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

Mergesort:

public static void mergesort(int[] data, int left, int right) {
    if (left < right){
        int middle = (left + right) / 2;
        mergesort(data, left, middle);
        mergesort(data, middle+1, right);
        merge(data, left, middle, right);
    }
}
private static void merge(int[] data, int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;
    int[] dataLeft = new int[n1];
    int[] dataRight = new int[n2];
    for (int i = 0; i < n1; i++)
        dataLeft[i] = data[left+i];
    for (int i = 0; i < n2; i++) 
        dataRight[i] = data[middle+1+i];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (dataLeft[i] <= dataRight[j]) {
            data[k] = dataLeft[i];
            i++;
        }
        else {
            data[k] = dataRight[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        data[k] = dataLeft[i];
        i++;
        k++;
    }
    while (j < n2) {
        data[k] = dataRight[j];
        j++;
        k++;
    }
}

For mergesort, it runs pretty well.

What is the reason? Would anyone please explain it?

More recursion steps or more state to store on the stack? – MrSmith42 Dec 13 '17 at 15:55 — MrSmith42, Dec 13 '17 at 15:55

MBo · Accepted Answer · 2017-12-13T15:59:12.700

This behavior is expectable for chosen partition scheme with pivot int pivot = data[low]; and sorted (or mostly) array - in such case stack depth might reach N=length of array.

You have to learn about more wise pivot choice - median of three or random pivot index. These approaches diminish probability of bad behavior for special data sets (but don't get rid it completely)

The second step - optimize recursion scheme:

To make sure at most O(log n) space is used, recurse first into the smaller side of the partition, then use a tail call to recurse into the other. So just compare (p-low) and high-p and choose right order of these calls:

    quicksort(data, low, p);
    quicksort(data, p + 1, high);

These issues and more solutions for them are shortly explained at the Wiki page and in details - in any algorithmic book/course

Note that mergesort always provides maximal stack depth log(N)

My input was mostly sorted array. According to Wikipedia, I changed the pivot[low] to pivot[low + (high-low)/2]. Now it works. — Jobayer Ahmmed, Dec 13 '17 at 16:14

Qucksort gets StackOverflowError for 100000 elements but mergesort does not in Java

1 Answers1