Quick Sort stackoverflow error for large arrays

Question

So I was assigned to implement a quick sort algorithm and compare the running times for arrays with size 500, 3500, and 80000. The arrays are populated with random numbers:

(int)Math.random()*1000000

My quicksort algorithm works for the arrays with size 500 and 3500, but I always get a stackoverflow error when I try to sort the third array with size 80000. My other sorting algorithms handle these arrays just fine.

My quick sort method:

public static void quickSort(int[] a, int p, int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quickSort(a,p,q);
        quickSort(a,q+1,r);
    }
}

My partition method:

private static int partition(int[] a, int p, int r) {

    int x = a[p];
    int i = p;
    int j = r;

    while (true) {
        do {
            i++;
        } while (i < r && a[i] < x);
        do {
            j--;
        } while (j > p && a[j] > x);

        if (i < j) {
            int tmp = a[i];
            a[i++] = a[j];
            a[j--] = tmp;
        } else {
            return j;
        }
    }
}

I read that I could simply change my stack size in the VM options (not sure how to do that) but that is just ignoring the problem in my algorithm. What's causing the error? Thanks!

My driver class:

public class Driver {

    public static void main(String[] args) {

        int[] array1 = new int[500];
        int[] array2 = new int[3500];
        int[] array3 = new int[80000];

        for(int i=0; i<array1.length; i++) {
            array1[i]=(int)(Math.random()*100000);
        }

        for(int i=0; i<array2.length; i++) {
            array2[i]=(int)(Math.random()*100000);
        }

        for(int i=0; i<array3.length; i++) {
            array3[i]=(int)(Math.random()*100000);
        }

        //~~~~~~~~~~~INSERTION~~~~~~~~~~~~~~~//

        System.out.println("INSERTION SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.INSERTION,array3)+" ms");

        //~~~~~~~~~~~BUBBLE~~~~~~~~~~~~~~~//

        System.out.println("\n\nBUBBLE SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.BUBBLE,array3)+" ms");

        //~~~~~~~~~~~MERGE~~~~~~~~~~~~~~~//

        System.out.println("\n\nMERGE SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.MERGE,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.MERGE,array3)+" ms");

        //~~~~~~~~~~~QUICK~~~~~~~~~~~~~~~//

        System.out.println("\n\nQUICK SORT:\n_______________");
        System.out.println("500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array1)+" ms");
        System.out.println("3500 Elements: "+SortTimes.runTime(SortTimes.QUICK,array2)+" ms");
        System.out.println("80000 Elements: "+SortTimes.runTime(SortTimes.QUICK,array3)+" ms");
    }
}

Here is my SortTimes class:

public class SortTimes {

    public final static int MERGE = 1;
    public final static int QUICK = 2;
    public final static int BUBBLE = 3;
    public final static int INSERTION = 4;

    public static double runTime(int sortMethod, int[] array) {

        double startTime;
        double endTime;

        switch(sortMethod) {
            case MERGE:
                startTime = System.currentTimeMillis();
                lab12.mergeSort(array);
                endTime = System.currentTimeMillis();
                break;

            case QUICK:
                startTime = System.currentTimeMillis();
                lab12.quickSort(array, 0, array.length-1);
                endTime = System.currentTimeMillis();
                break;

            case BUBBLE:
                startTime = System.currentTimeMillis();
                lab12.bubbleSort(array);
                endTime = System.currentTimeMillis();
                break;

            case INSERTION:
                startTime = System.currentTimeMillis();
                lab12.insertionSort(array);
                endTime = System.currentTimeMillis();
                break;

            default:
                startTime = -1;
                endTime = 0;
                break;
        }

        return endTime-startTime;
    }
}

Answer 1

If quickSort() is still using pivot x = a[p], and not x = a[(p+r)/2], then if the data is already sorted, quickSort() will probably get stack overflow. Any chance that you're running quickSort() on data that's already been sorted by a prior sort?