public class cQuickSort {	
	public static void main(String argv[]) {		
		int limit = Integer.parseInt(argv[0]);
		int i[] = new int[limit];
		
		int noThreadsStartup = Thread.currentThread().getThreadGroup().activeCount();

		for (int c=0; c<limit; c++)
			i[c]=(int) (Math.random()*limit);
			
		displayArray(i,0,i.length-1);	
		
		new Thread(new QuickSort(i,0,i.length-1)).start();
		
		while (Thread.currentThread().getThreadGroup().activeCount() > noThreadsStartup);
		
		displayArray(i,0,i.length-1);		
	} //main()
  
	private static void displayArray(int[] a, int l, int r) {
  		for(int i=l;i<r-l+1;i++) 
      	System.out.print(a[i]+" ");
    	System.out.println();
  	} //displayArray()
} //class cQuickSort

class QuickSort implements Runnable {
	int a[];
	int l;
	int r;
	public QuickSort(int[] a, int l, int r) {
		this.a = a;
		this.l = l;
		this.r = r;
	} //constructor
	
	private static void swap(int[] a, int s, int d) {
		int tmp = a[s];
		a[s] = a[d];
		a[d] = tmp;
	} //swap();
	
	public void run() {
		System.out.println(Thread.currentThread().getName()+" l="+l+", r="+r);
      int i=l;
      int j=r;
      int k = (int) ((l+r)/2);
      System.out.println(Thread.currentThread().getName()+" pivot="+k+" (value="+a[k]+")");
      int pivot = a[k];
      do {
        while(a[i] < pivot)
          i++;
        while(pivot < a[j])
          j--;
        if(i<j && a[i] != a[j]) {
          System.out.println(Thread.currentThread().getName()+" exchanging a["+i+"] (="+a[i]+") and a["+j+"] (="+a[j]+")");
          swap(a,i,j);
        } //if
        if (i<=j) {
			 i++;
          j--;
		  } //if
      } while (i<j);    

      if (l<j) {
      	System.out.println(Thread.currentThread().getName()+" child: l="+l+", r="+j);
      	new Thread(new QuickSort(a,l,j)).start();
      } //if
      if (i<r) {
      	System.out.println(Thread.currentThread().getName()+" child: l="+i+", r="+r);
      	new Thread(new QuickSort(a,i,r)).start();
      } //if
   } //run
} //class QuickSort