How to fix StackOverflow error while using Quicksort for big arrays?

Question

I'm doing a benchmark for different sorting and I'm getting a StackOverflowError using Quicksort for an array of size 100,000.

private static int partition(int a[], int start, int end) {
    int pivot = a[end];
    int i = (start - 1);

    for (int j = start; j <= end - 1; j++) {
        if (a[j] < pivot) {
            i++;
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    int t = a[i + 1];
    a[i + 1] = a[end];
    a[end] = t;
    return (i + 1);
}

//Quick Sort
public static long quickSort(int a[], int start, int end) {
    long comeco = System.currentTimeMillis();
    if (start < end) {
        int p = partition(a, start, end);
        quickSort(a, start, p - 1);   <<< ------------- Here s where I got the error
        quickSort(a, p + 1, end);
    }
    long tempo = System.currentTimeMillis() - comeco;
    return tempo;
}

I will also need to use Quicksort to sort an array of size 1,000,000 so I will get this problem again.

I read about increasing the stack size but didn't figure out how to do it properly.

possible duplicate? https://stackoverflow.com/questions/30406242/quicksort-stack-overflow-on-big-input — Dennis LLopis, Nov 06 '22 at 03:29

score 0 · Accepted Answer · answered Nov 06 '22 at 07:23

To limit stack space to O(log(n)), recurse on smaller partition, loop back on larger partition. Worst case time complexity remains O(n^2)).

    while (start < end) {
        int p = partition(a, start, end);
        if((p - start) <= (end - p)){
            quickSort(a, start, p - 1);
            start = p + 1;
        } else {
            quickSort(a, p + 1, end);
            end = p - 1;
    }

How to fix StackOverflow error while using Quicksort for big arrays?

1 Answers1