Optimizing quick sort

Question

I am implementing quick sort algorithm in java and here is the code :

public class quickSort {
      private int array[];
    private int length;

    public void sort(int[] inputArr) {

        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSorter(0, length - 1);
    }

    private void quickSorter(int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;

        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {

            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSorter(lowerIndex, j);
        if (i < higherIndex)
            quickSorter(i, higherIndex);
    }

    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}

Then I implement it with (median of three)

public class quickSort {
      private int array[];
private int length;

public void sort(int[] inputArr) {

    if (inputArr == null || inputArr.length == 0) {
        return;
    }
    this.array = inputArr;
    length = inputArr.length;
    quickSorter(0, length - 1);
}

private void quickSorter(int lowerIndex, int higherIndex) {

    int i = lowerIndex;
    int j = higherIndex;
    int mid = lowerIndex+(higherIndex-lowerIndex)/2;
    if (array[i]>array[mid]){
       exchangeNumbers( i,  mid);
    }
    if (array[i]>array[j]){
       exchangeNumbers( i,  j);
    }
    if (array[j]<array[mid]){
       exchangeNumbers( j, mid);
    }

    int pivot = array[mid];
    // Divide into two arrays
    while (i <= j) {

        while (array[i] < pivot) {
            i++;
        }
        while (array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchangeNumbers(i, j);
            //move index to next position on both sides
            i++;
            j--;
        }
    }
    // call quickSort() method recursively
    if (lowerIndex < j)
        quickSorter(lowerIndex, j);
    if (i < higherIndex)
        quickSorter(i, higherIndex);
}

private void exchangeNumbers(int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
}

and the testing main :

public static void main(String[] args) {
        File number = new File ("f.txt");
        final int size = 10000000;

        try{
            quickSortOptimize opti = new quickSortOptimize();
             quickSort s = new quickSort();
        PrintWriter printWriter  = new PrintWriter(number);
         for (int i=0;i<size;i++){
            printWriter.println((int)(Math.random()*100000));
        }
         printWriter.close();
        Scanner in = new Scanner (number);
        int [] arr1 = new int [size];
        for (int i=0;i<size;i++){
          arr1[i]=Integer.parseInt(in.nextLine());
        }
        long a=System.currentTimeMillis();
        opti.sort(arr1);
        long b=System.currentTimeMillis();
        System.out.println("Optimaized quicksort: "+(double)(b-a)/1000);
        in.close();
        int [] arr2 = new int [size];
        Scanner in2= new Scanner(number);
        for (int i=0;i<size;i++){
          arr2[i]=Integer.parseInt(in2.nextLine());
        }
         long c=System.currentTimeMillis();
         s.sort(arr2); 
        long d=System.currentTimeMillis();
         System.out.println("normal Quicksort: "+(double)(d-c)/1000);
        }catch (Exception ex){ex.printStackTrace();}

    }

The problem is that this method of optimization should improve performance by 5%

but, what happens actually is that I have done this test many times and almost always getting better result on normal quicksort that optimized one

so what is wrong with the second implementation

Answer 1

A median of three (or more) will usually be slower for input that's randomly ordered.

A median of three is intended to help prevent a really bad case from being quite as horrible. There are ways of making it pretty bad anyway, but at least avoids the problem for a few common orderings--e.g., selecting the first element as the pivot can produce terrible results if/when (most of) the input is already ordered.