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

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.

Answer

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;
    }