Quicksort algorithm fails on StackOverflow error

Question

I am working on a modified version of Quicksort which uses a formula of ((lowIndex + highIndex) / 2) to decide it's partition.

My code is below. However, whenever I run it, I get the following error:

start ARRAY
1
2
10
9
3
4
8
7
5
6
Exception in thread "main" java.lang.StackOverflowError
        at newQuickSort.quicksort(newQuickSort.java:37)
        at newQuickSort.quicksort(newQuickSort.java:39)

Where the line at newQuickSort.quicksort(newQuickSort.java:39) is repeated.

Essentially, I am simply trying to change the partition function to use median-of-three partitioning, and not really touch the Quicksort algorithm at all, just the Partition function.

I am not exactly sure why this error is occurring, though I have referenced the following:

• https://www.geeksforgeeks.org/quick-sort/
• median of three values strategy
• https://codereview.stackexchange.com/questions/150719/quicksort-median-of-three-v2

Any advice would be helpful, thanks!

public class newQuickSort{ 

    static int count;

    static void move(int myArray[], int a, int b){
        int temp;
        temp = myArray[a];
        myArray[a] = myArray[b];
        myArray[b] = temp;
    } //end move

    //Create the partition function
    static int partition(int myArray[], int p, int r){
        int medIndex = (p+r) / 2;
        int pivot;

            if (myArray[p] > myArray[medIndex]){
                move(myArray, p, medIndex); 
            }else if (myArray[p] > myArray[r]){
                move(myArray, p, r);
            }else if (myArray[medIndex] > myArray[r]){
                move(myArray, medIndex, r);
            }
            //end if checks

            //now set proper movements
            move(myArray, medIndex, r-1);
            //set pivot
            pivot = myArray[r-1];
            //return pivot for which to partition around
            return pivot;
    } //end partition 

    static void quicksort(int myArray[], int p, int r){ 
        if (p < r){
        checkCount += 1; 
            int partition = partition(myArray, p, r); 
            quicksort(myArray, p, partition-1); 
            quicksort(myArray, partition+1, r); 
        } //end if 
    } //end quicksort

    public static void main (String[] args){
        int testarray[] = {1,2,10,9,3,4,8,7,5,6};
       // int testarray[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        System.out.println("start ARRAY");
        for (int i = 0; i < testarray.length; i++){
            System.out.println(testarray[i]);
        } //end for

        int p = 0;
        int r = testarray.length-1;
        newQuickSort mySort = new newQuickSort();
        mySort.quicksort(testarray, p, r);

        System.out.println("end ARRAY");
        for (int j = 0; j < testarray.length; j++){
            System.out.println(testarray[j]);
         } //end for

    }
}

Answer 1

Your partition function returns the value of the pivot. But its caller (quicksort) is expecting the index of the pivot.

The termination of the recursion depends on the partition point being in the index range.

Once you fix that, consider optimising quicksort to minimise stack usage:

1. First, recurse to sort the smaller range (in the sense of having fewer elements).

2. Then loop to to continue with the larger range.

That guarantees that the recursion depth is no more than log₂N.