// QuickSort: carries out quicksort
public class QuickSort {
   private double[] a; // holds numbers for sorting
   private int size; // size of array

   public QuickSort(int s) {
      size = s;
      a = new double[size];
   }

   public void generateNumbers() {
      for (int i = 0; i < size; i++) // generate numbers to sort
         a[i] = Math.random();
   }

   public void swapRef(int i, int j) {
      double temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   public void quicksort() {
      quicksort(0, a.length - 1);
   }

   public void quicksort(int low, int high) {
      // System.out.print("In quicksort: " + low + " " + high + ", ");
      // printArray(); System.out.println();
      if (high >low) {
         int pivot = partition(low, high);
         quicksort(low, pivot-1);
         quicksort(pivot+1, high);
       }
   }
   
   public int partition(int low, int high) {
      int left, right;
      double pivot_item = a[low];
      int pivot = left = low;
      right = high;
      while ( left < right ) {
         while(left < a.length - 1 &&
               a[left] <= pivot_item) // Move left while item < pivot
            left++;
         while(a[right] > pivot_item) // Move right while item > pivot
            right--;
         if (left < right) swapRef(left,right);
      }
      // right is final position for the pivot */
      a[low] = a[right];
      a[right] = pivot_item;
      return right;
   }

   public boolean checkSorted() { // check if in sorted order
      for (int i = 0; i < size-1; i++)
         if (a[i] >= a[i+1]) return false;
      return true;
   }
}

// QuickSortTest: test the QuickSort class
public class QuickSortTest {
   final static int SIZE = 5120000;

   public static void main(String[] argv) {
      QuickSort q = new QuickSort(SIZE);
      System.out.println("Number of items: " + SIZE);
      long startTime = System.currentTimeMillis();
      q.generateNumbers();
      elapsedTime(startTime, "After generating, ");
      q.quicksort();
      elapsedTime(startTime, "After sorting (quicksort), ");
      System.out.println("Sorted is " + q.checkSorted());
   }

   public static void elapsedTime(long startTime, String s) {
      long stopTime = System.currentTimeMillis();
      double elapsedTime = ((double)(stopTime - startTime))/1000.0;
      System.out.println(s + "elapsed time: " + elapsedTime + " seconds");
   }
}

Number of items: 5120000
After generating, elapsed time: 3.949 seconds
After sorting (quicksort), elapsed time: 20.213 seconds
Sorted is true

Number of items: 2560000
After generating, elapsed time: 2.003 seconds
After sorting (quicksort), elapsed time: 9.499 seconds
Sorted is true

Number of items: 1280000
After generating, elapsed time: 1.112 seconds
After sorting (quicksort), elapsed time: 4.767 seconds
Sorted is true

Number of items: 640000
After generating, elapsed time: 0.599 seconds
After sorting (quicksort), elapsed time: 2.316 seconds
Sorted is true