Stack overflow error with Quicksort and median implementation

Question

First of all I'm just going to state that this is a homework question which I have made an extensive amount of attempts on.

I've been asked to modify quicksort in Java to set the pivot as the psuedo median of 9 values in the array using the formula i * (n-1) /8

I wrote a computeMedian method which accepts 3 integers, determines the highest, and then returns that value.

The code:

public static int computeMedian(int x, int y, int z)
    {
        if((x >= y && x <= z) || (x >= z && x <= y)) {return x;}
        else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;}
        else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;}
        else { return 0; }
    }

I then used it in my findPivot method which takes the current array, from, to values and uses them to construct a pivot

Here is that code:

public static int findPivot(int[] a, int from, int to)
    {
        if(a.length <= 7)
        {
            return a[(to)/2];
        }
        else if(a.length > 7 && a.length <= 40)
        {
            return computeMedian(a[from], a[(to)/2] , a[to]);
        }
        else
        {
            int x = computeMedian(a[0 * (to) / 8], a[1 * (to) / 8], a[2 * (to) / 8]);
            int y = computeMedian(a[3 * (to) / 8], a[4 * (to) / 8], a[5 * (to) / 8]);
            int z = computeMedian(a[6 * (to) / 8], a[7 * (to) / 8], a[8 * (to) / 8]);
            return computeMedian(x,y,z);
        }
    }

This method is working fine for sorting any array less than or equal to size 40, but as soon as it gets larger than 40 I recieve a stack overflow error leading back to my computeMedian method in the else {} portion. I will note that return computeMedian(a[from], a[(to)/2] , a[to]); works in the > 40 portion if I put it there, but that is only the median of 3 values as opposed to the median of the median of 3 sets.

Currently this is how I have findPivot plugged into the quicksort partitioning method:

private static int modPartition(int[] a, int from, int to)
    {
        int pivot = findPivot(a, from, to);
        int i = from - 1;
        int j = to + 1;
        while(i < j)
        {
            i++; while (a[i] < pivot) { i++; }
            j--; while (a[j] > pivot) { j--; }
            if (i < j) { swap(a, i, j); }
        }
        return j;
    }

I'm pretty much stumped on why my computeMedian method fails to work on larger datasets. I've tried placing the i * (n-1) / 8 values in an array via a for loop, sorting them and returning the value in the middle as well as placing the values in an array p and calling computeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etc and I get the same stack overflow issue but it tends to move around to different portions of my code and leading me in circles.

I can post any more snippets if anyone needs but I think my issue is right here probably.

Thanks for the help. I'm still learning and I think getting a grip on this would totally help me problem solve in the future on my own.

Here are the problem lines from the stack trace: Line 16: int p = modPartition(a, from, to); Line 18 modSort(a, p+1, to); Line 23 int pivot = findPivot(a, from, to);

Heres my entire modSort method also:

public static void modSort(int[]a, int from, int to)
    {
        if(from >= to) { return; }
        int p = modPartition(a, from, to);
        modSort(a, from, p);
        modSort(a, p+1, to);
    }

Answer 1

Reproduced and corrected

Code added to reproduce the error ...

private static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

public static void main(String[] args) {
    // Generate a sample
//      ArrayList<Integer> list = new ArrayList<>(64);
//      for (int i = 0; i < 64; i++) list.add(i);
//      Collections.shuffle(list);
//      System.out.println(list);
    int[] arr = {40, 9, 2, 62, 8, 42, 46, 23, 61, 45, 63, 48, 43, 36, 33, 32, 1, 55, 7, 17, 16, 25, 5, 26, 22, 11, 56, 38, 60, 31, 58, 29, 51, 34, 24, 54, 4, 3, 30, 20, 57, 18, 50, 44, 41, 12, 59, 6, 53, 39, 37, 35, 28, 13, 14, 15, 0, 19, 49, 52, 21, 27, 47, 10};

    modSort(arr, 0, arr.length-1);

    System.out.println(Arrays.toString(arr));
}

Debugging. Setting breakpoint for StackOverFlowError (as suggested in comments) didn't work. So I go for a regular breakpoint at line (start of modSort).

For this sample data starts doing infinite recursion over modSort with from=3;to=5. For that range the pivot p=2, which seems abnormal.

I blame findPivot(a,from,to) method. Looks good for finding a pivot for the whole a, but not for a range. Trying this correction:

public static int findPivot(int[] a, int from, int to) {
    final int rangeLength = to - from + 1;
    if(rangeLength <= 7) {
        return a[(from + to)/2];
    } else if(rangeLength  <= 40) { // why test "a.length > 7" ?
        return computeMedian(a[from], a[(from + to)/2] , a[to]);
    } else {
        final int rangeLength_8 = (to - from) / 8;
        int x = computeMedian(a[from], a[from + rangeLength_8], a[from + 2 * rangeLength_8]);
        int y = computeMedian(a[from + 3 * rangeLength_8], a[from + 4 * rangeLength_8], a[from + 5 * rangeLength_8]);
        int z = computeMedian(a[from + 6 * rangeLength_8], a[from + 7 * rangeLength_8], a[to]);
        return computeMedian(x,y,z);
    }
}

Then it works fine for my example. I stop it at this point (have to get some sleep).

I think you should try to get familiar with the debugger. I think it should had been easier for you to figure it out.