Modifying quicksort to quicksort using to use pivot 'median of three'

Question

I am trying to modify a Quicksort program that used the first element as pivot to a Quicksort that uses the median of three (median of first, last and middle element) as pivot. My implementation thus far is however giving me ArrayIndexOutOfBoundsException(s) when testing it. I guess I am missing something here, but I just can't figure out where I'm wrong. Any help and advice is highly appreciated.

public class Sorts {

    private static void swap(int[] array, int index1, int index2) {
        // Precondition: index1 and index2 are >= 0 and < SIZE.
        //
        // Swaps the integers at locations index1 and index2 of the values array. 
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }

    private static int medianOfThree(int[] array, int first, int last) {

        int mid = array[(first+last)/2];

        if (array[first] > array[mid]) {
            swap(array, first, mid);
        }

        if (array[first] > array[last]) {
            swap(array, first, last);
        }

        if (array[mid] > array[last]) {
            swap(array, mid, last);
        }
        swap(array, mid, last-1);
        return array[last-1];
    }

    private static int partition(int[] array, int first, int last, int median) {

        int pivot = array[last-1];
        int saveF = last-1;
        boolean onCorrectSide;

        first++;
        do {
            onCorrectSide = true;
            while (onCorrectSide) {           // move first toward last
                if (array[first] > pivot) {
                    onCorrectSide = false;
                }
                else {
                    first++;
                    onCorrectSide = (first <= last);
                }
            }

            onCorrectSide = (first <= last);
            while (onCorrectSide) {         // move last toward first
                if (array[last] <= pivot) {
                    onCorrectSide = false;
                }
                else {
                    last--;
                    onCorrectSide = (first <= last);
                }
            }

            if (first < last) {
                swap(array, first, last);
                first++;
                last--;
            }
        } while (first <= last);

        swap(array, saveF, last);
        return last;
    }


    private static void quickSort(int[] array, int first, int last) {

        if (first < last) {
            int pivot;

            int median = medianOfThree(array, first, last); 
            pivot = partition(array, first, last, median);

            // values[first]..values[splitPoint - 1] <= pivot
            // values[splitPoint] = pivot
            // values[splitPoint+1]..values[last] > pivot

            quickSort(array, first, pivot - 1);
            quickSort(array, pivot + 1, last);
        }
    }


    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length-1);
    }
}

Answer 1

you are not using the variable in the right way:

 int mid = array[first+last/2];

gives you the value in mid of the array, but not the offset (index) of the array. But you are using mid, as index variable in your calls of the methods:

swap(array, first, mid);