static void MergeSort(int[] A, int p, int r) {
		
		if (p < r) {
			if((r-p)>11){
				int q = p + ((r-p)>>1);	// Get the medium element by shifting
				MergeSort(A, p, q);
				MergeSort(A, q+1, r);
				Merge(A, p, q, r);
			} else {  // Insertion sort
				for(int i=p, j=i; i<r; j=++i) {
				    int ai = A[i+1];
				    while(ai < A[j]) {
				    	A[j+1] = A[j];
				    	if (j-- == p) {
				    		break;
				    	}
				    }
				    A[j+1] = ai;
				}
			 }
        }
    }