import java.util.Arrays;

public class Quick {
      
   // sort data[first]..data[first+n-1] into ascending order      
   public static void quickSort (int [] data, int first, int n) {
      if (n>1) {
         final int pivot_index = partition (data, first, n);
         final int n1 = pivot_index - first;   // length of first part
         final int n2 = n-n1-1;                // length of second part

         //  The pivot element is now at index "pivot_index".  It is now already
         //  in its correct position, hopefully in the middle of the array.

         quickSort (data, first, n1);         // Sort data[first..pivot_index-1], len=n1
         quickSort (data, pivot_index+1, n2); // Sort data[pivot_index+1..first+n-1], len=n2
      }
   }

   /*
     paritition data[first..first+n-1] into values <= data[first] and > data[first]
   */

   public static int partition (int [] data, int first, int n) {
      final int pivot = data[first];

      int tooBigIndex=first+1, tooSmallIndex=first+n-1;
      while (tooBigIndex <= tooSmallIndex) {

         // data[first .. tooBigIndex-1] <= pivot
         // data[tooSmallIndex+1 .. first+n-1] > pivot

         while (tooBigIndex < first+n && data[tooBigIndex]<=pivot) tooBigIndex++;
         while (data[tooSmallIndex] > pivot) tooSmallIndex--;

         if (tooBigIndex<tooSmallIndex) {
            swap (data, tooBigIndex, tooSmallIndex);
         }
      }

      // Move the pivot element to its correct position at data[tooSmallIndex]
      data[first] = data[tooSmallIndex];
      data[tooSmallIndex] = pivot;

      return tooSmallIndex;  // index of pivot
   }

   private static void swap (final int [] data, final int i, final int j) {
      final int temp = data[i];
      data[i]=data[j];
      data[j]=temp;
   }

   public static void main (final String [] args) throws NumberFormatException {
      final int [] data  = new int [args.length];
      for (int i=0; i<data.length; i++) {
         data[i] = Integer.parseInt (args[i]);
      }

      System.out.printf ("..: %s%n", Arrays.toString(data));
      quickSort (data, 0, data.length);
      System.out.printf ("**: %s%n", Arrays.toString(data));
   }
}