Ttykuu

I implemented a standard quicksort and I have a project where I need to improve it. I am trying to make quicksort faster by implementing median of 3 partitioning. I copied codes from trusted educational sites and the code is working, everything is being sorted. The issue is that, the median of 3 partitioning is taking 20 milliseconds to 40 milliseconds more than the standard quicksort. I am sorting 10240000 integers, positive and negative. can anybody help me solve this out?

main class

package sorttest;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

public class SortTest 

public static void main(String[] args) throws FileNotFoundException, IOException 
 Clock c = new Clock();
 int lo = 0;
 int hi = 10239999;

 sort s = new sort();
 Option2 o = new Option2();

 int[] NumArray = populate();

 /*c.start();
 s.quick(NumArray, lo, hi);
 double time = c.stop();
 System.out.println("Improved quicksort takes " +time);*/
 int[] NumArrays = populate();
 c.start();
 s.quickiSort(NumArrays, lo, hi);
 double times = c.stop();
 System.out.println("Quicksort takes " + times);

 c.start();
 o.quickSort(NumArray, lo, hi);
 double time = c.stop();
 System.out.println("Improved quicksort takes " + time);

 /*for (int i =0; i<NumArray.length; i++)
 System.out.println(NumArray[i]);
 */


public static int[] populate() throws FileNotFoundException, IOException 
 String[] splitArr = split();
 int[] arr = new int[10240000];
 for (int i = 0; i < splitArr.length; i++) 
 int num = Integer.parseInt(splitArr[i]);
 arr[i] = num;
 
 return arr;


public static String[] split() throws FileNotFoundException, IOException 
 BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("C:\Users\username\Documents\year2\Engeneering Software Development\cw3\ints10240000.dat")));
 String line;
 String[] aList = new String[10240000];
 while ((line = reader.readLine()) != null) 
 aList = line.split("\s+");
 //String aList = (line.split("\s+"))); //using whitespace as delimeter to split 
 
 return aList;

Standard quicksort

 public void quickiSort(int arr[], int begin, int end) 
 if (begin < end) 
 int partitionIndex = partitionL(arr, begin, end);

 quickiSort(arr, begin, partitionIndex - 1);
 quickiSort(arr, partitionIndex + 1, end);
 



private int partitionL(int arr[], int begin, int end) 
 int pivot = arr[end];
 int i = (begin - 1);

 for (int j = begin; j < end; j++) 
 if (arr[j] <= pivot) 
 i++;

 int swapTemp = arr[i];
 arr[i] = arr[j];
 arr[j] = swapTemp;
 
 

 int swapTemp = arr[i + 1];
 arr[i + 1] = arr[end];
 arr[end] = swapTemp;

 return i + 1;

Median of 3 quicksort

package sorttest;

public class Option2 

public void quickSort(int[] theArray, int lo, int hi) 
 recQuickSort(theArray, lo, hi);


public void recQuickSort(int[] theArray, int left, int right) 
 int size = right - left + 1;
 if (size <= 3) 
 manualSort(theArray, left, right);
 else 
 long median = medianOf3(theArray, left, right);
 int partition = partitionIt(theArray, left, right, median);
 recQuickSort(theArray, left, partition - 1);
 recQuickSort(theArray, partition + 1, right);
 


public long medianOf3(int[] theArray, int left, int right) 
 int center = (left + right) / 2;

 if (theArray[left] > theArray[center]) 
 swap(left, center, theArray);
 

 if (theArray[left] > theArray[right]) 
 swap(left, right, theArray);
 

 if (theArray[center] > theArray[right]) 
 swap(center, right, theArray);
 

 swap(center, right - 1, theArray);
 return theArray[right - 1];


public void swap(int dex1, int dex2, int[] theArray) 
 int temp = theArray[dex1];
 theArray[dex1] = theArray[dex2];
 theArray[dex2] = temp;


public int partitionIt(int[] theArray, int left, int right, long pivot) 
 int leftPtr = left;
 int rightPtr = right - 1;

 while (true) 
 while (theArray[++leftPtr] < pivot) 
 ;
 while (theArray[--rightPtr] > pivot) 
 ;
 if (leftPtr >= rightPtr) 
 break;
 else 
 swap(leftPtr, rightPtr, theArray);
 
 
 swap(leftPtr, right - 1, theArray);
 return leftPtr;


public void manualSort(int[] theArray, int left, int right) 
 int size = right - left + 1;
 if (size <= 1) 
 return;
 
 if (size == 2) 
 if (theArray[left] > theArray[right]) 
 swap(left, right, theArray);
 
 return;
 else 
 if (theArray[left] > theArray[right - 1]) 
 swap(left, right - 1, theArray);
 
 if (theArray[left] > theArray[right]) 
 swap(left, right, theArray);
 
 if (theArray[right - 1] > theArray[right]) 
 swap(right - 1, right, theArray);