import java.util.Random;
	
public class QuickSort {

	public int[] medianQuickSort(int[] q) {
	   int[] less, pivotList, greater;
	   int pivotMedian;
	   if(q.length <= 1) {
	      return q;
	   }
	   pivotMedian=getMedian(q[0], q[Math.floor(q.length/2)], q[q.length-1]);

	   for(int i=0; i<q.length; i++) {
	      if(q[i] < q[pivotMedian]) {
	         less[i] = q[i];
	      } else if(q[i] >= q[pivotMedian]) {
	         greater[i] = q[i];
	      }
	   }
	   pivotList[] = pivotMedian;
	   return concatenate(randomQuickSort(less), pivotList, randomQuickSort(greater));
	}

	private int getMedian(int a, int b, int c) {
	   return Math.min(Math.max(a, b), Math.min(Math.max(a, c), Math.max(b, c)));
	}

	public int[] randomQuickSort(int[] q) {
	   int[] less, pivotList, greater;
	   int pivotIndex;
	   if(q.length <= 1) {
	      return q;
	   }
	   Random pivot = new Random();
	   pivotIndex=pivot.nextInt(q.length);

	   for(int i=0; i<q.length; i++) {
	      if(i != pivotIndex && q[i] < q[pivotIndex]) {
	         less[i] = q[i];
	      } else if(i != pivotIndex && q[i] >= q[pivotIndex]) {
	         greater[i] = q[i];
	      }
	   }
	   pivotList[] = q[pivotIndex];
	   return concatenate(randomQuickSort(less), pivotList, randomQuickSort(greater));
	}
	
	private int[] concatenate(int[] n1, int[] n2, int[] n3) {
		int[] merger = new int[n1.length+n2.length+n3.length];
		for(int i=0; i<n1.length; i++) {
			merger[i] = n1[i];
		}
		for(int i=1; i<=n2.length; i++) {
			merger[i+n1.length] = n2[i];
		}
		for(int i=1; i<=n3.length; i++) {
			merger[i+n1.length+n2.length] = n3[i];
		}		
		return merger;
	}
}