import java.util.Random;

class qsort {
    private static void sort(int a[], int loOld, int hiOld)
    {
	int low = loOld;
	int high = hiOld;
        int pivot;

	if (low >= high)
	    return;
        else if ( low == (high - 1) )
        {
            // sort a two element list by swapping if necessary 
            if (a[low] > a[high]) {
                int temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
            return;
	}

        // pivot selection
       pivot = a[(low + high) / 2];
       a[(low + high) / 2] = a[high];
       a[high] = pivot;

//      pivot = a[high];

//       Random generator = new Random();
//       int randomposition = generator.nextInt((high +1) - low) + low;
//       pivot = a[randomposition];
//       a[randomposition] = a[high];
//       a[high] = pivot;

        while ( low < high ) {
            // Search forward from a[lo] until an element is found that
            // is greater than the pivot or low >= high 
            while ( (a[low] <= pivot) && (low < high) )
		low++;

            // Search backward from a[hi] until element is found that
            // is less than the pivot, or low >= high
	    while ( (pivot <= a[high]) && (low < high) )
		high--;

            // Swap elements a[low] and a[high]
            if( low < high ) {
                int temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
	}

        // Put the median in the "center" of the list
        a[hiOld] = a[high];
        a[high] = pivot;

        // recursive call on both pieces
	sort(a, loOld, low - 1);
	sort(a, high + 1, hiOld);
    }

    private static void sort(int a[]) {
	sort(a, 0, a.length-1);
    }

    public static void main (String[] args)
    {
       Random generator = new Random();
       int[] v = new int[10000];

       for (int i = 0; i < 10000; i++)
         v[i] = generator.nextInt(10000) + 1;

       System.out.println("array unsorted ");

       long runtime = System.currentTimeMillis();
       sort(v);
       runtime = System.currentTimeMillis() - runtime;

       System.out.println("array sorted ");

       System.out.println("Total runtime " + runtime);

       runtime = System.currentTimeMillis();
       sort(v);
       runtime = System.currentTimeMillis() - runtime;

       System.out.println("array sorted again");

//       for (int i = 0; i < v.length; i++)
//         System.out.print(v[i] + " ");
//       System.out.println();

       System.out.println("Total runtime " + runtime);
    }
}