/* Originally based on http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html */

public class Quicksort  {
    private double[] numbers;

    public static void sort(double[] values) {
        // Check for empty or null array
        if (values==null || values.length==0){
            return;
        }
        new Quicksort( values ).quicksort(0, values.length-1);
    }

    private void quicksort(int low, int high) {
        int i = low, j = high;
        double pivot = this.numbers[low];

        // Partition into two lists:
        // On the left, everything less than the pivot, and 
        // on the right, everything more than the pivot.
        while (i <= j) {
            // Advance i to the first number that isn't less than the pivot.
            // (This is a number that *shouldn't* be on the left.)
            while (numbers[i] < pivot) { ++i; }
            while (numbers[j] > pivot) { --j; }

            // If we have found a value in the left list which is larger then
            // the pivot element, and we have found a value in the right list
            // which is smaller then the pivot element, then we exchange the
            // values.  Then 
            // As we are done we can increase i and j
            if (i <= j) {
                swapAt(i, j);
                i++;
                j--;
            }
        }
        
        // Recursion
        if (low < j)
            quicksort(low, j);
        if (i < high)
            quicksort(i, high);
    }

    private void swapAt(int i, int j) {
        double temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
    
    
    static double[] makeRands( int sz ) {
      double[] data = new double[sz];
      for (int i=0; i<data.length; ++i) {
        data[i] = Math.random();
        }
      return data;
     }

    static boolean nondecreasing( double[] nums ) {
      boolean nonDecrSoFar = true;
      for (int i=0; i+1<nums.length && nonDecrSoFar; ++i) {
        nonDecrSoFar = nonDecrSoFar && (nums[i] <= nums[i+1]);
        }
      return nonDecrSoFar;
      }
     
    static long testAndTime( double[] nums ) {
      long t0 = System.currentTimeMillis();
      sort(nums);
      long t1 = System.currentTimeMillis();
      if (! nondecreasing(nums)) {
        System.err.println( "Sort failed!" );
        }
      return (t1-t0);
      }
        
    public static void main( String[] args ) {
       System.gc();
       System.gc();
       System.gc();
       int sz = 1000;
       while (sz <= 10000000) {
         long t = testAndTime( makeRands(sz) );
         System.out.printf( "For a list of size %d: %dms.\n", sz, t );
         sz *= 10;
         }
      }
      
    static void printArrayStart( double[] nums, int stop ) {
      System.out.print("[");
      for (int i=0;  i<stop && i<nums.length;  ++i) {
        if (i!=0) System.out.print(", ");
        System.out.print(nums[i]);
        }
      System.out.println("]");
      }
      
      
    Quicksort( double[] _numbers ) { this.numbers = _numbers; }
   }