big difference in time between two Implementation of quick Sort
<p>I have two implementation of quick sort the first one uses a median of (fist ,middle , last ) as pivot and the second uses the middle element as pivot 
the first Implementation :</p>

<pre><code>public class quickMedian {
     public void sort(int array[]) 
// pre: array is full, all elements are non-null integers
// post: the array is sorted in ascending order
{
    quickSort(array, 0, array.length - 1);              // quicksort all the elements in the array
} 
public void quickSort(int array[], int start, int end)
{
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start &gt;= 1)                   // check that there are at least two elements to sort
        {
                if (array[start+(end-start)/2]&gt;array[end]){
                    swap(array,start+(end-start)/2, end);
                }
                if (array[start]&gt;array[end]){
                    swap(array,start, end);
                }
                if (array[start+(end-start)/2]&gt;array[start]){
                    swap(array, start+(end-start)/2, start);
                }

                int pivot = array[start];       // set the pivot as the first element in the partition

                while (k &gt; i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] &lt;= pivot &amp;&amp; i &lt;= end &amp;&amp; k &gt; i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] &gt; pivot &amp;&amp; k &gt;= start &amp;&amp; k &gt;= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k &gt; i)                                       // if the left seekindex is still smaller than
                                swap(array, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array, start, k);          // after the indices have crossed, swap the last element in                                               // the left partition with the pivot 
                quickSort(array, start, k - 1); // quicksort the left partition
                quickSort(array, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}

public void swap(int array[], int index1, int index2) 
// pre: array is full and index1, index2 &lt; array.length
// post: the values at indices 1 and 2 have been swapped
{
    int temp = array[index1];           // store the first value in a temp
    array[index1] = array[index2];      // copy the value of the second into the first
    array[index2] = temp;               // copy the value of the temp into the second
}


}
</code></pre>

<p>The second Implementation :</p>

<pre><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 &lt;= j) {
            /**
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.
             */
            while (array[i] &lt; pivot) {
                i++;
            }
            while (array[j] &gt; pivot) {
                j--;
            }
            if (i &lt;= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex &lt; j)
            quickSorter(lowerIndex, j);
        if (i &lt; higherIndex)
            quickSorter(i, higherIndex);
    }

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

}
</code></pre>

<p>To obtain the median we need to do extra steps on each recursion which may increase the time <strong>a little bit</strong> (if the array is totally random) .</p>

<p>I am testing these two classes on an array of size <code>N=10,000,000</code> randomly generated  and I have done the test many times the first Implementation takes around 30 seconds and the second takes around 4 seconds 
so this is  obviously not caused by the extra overhead to get the median of three numbers .</p>

<p>There must be something wrong with the first implementation, what is it ?</p>

<p>here is the testing code :</p>

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

    try{
   //  quickSort s = new quickSort();
     quickMedian s = new quickMedian();
    writeTofile(number, size);
  int [] arr1 =readFromFile(number, size);
    long a=System.currentTimeMillis();
    s.sort(arr1);
    long b=System.currentTimeMillis();
    System.out.println("quickSort: "+(double)(b-a)/1000);
    }catch (Exception ex){ex.printStackTrace();}


 }
</code></pre>