Int n1 = q - p + 1; // size of left array

int n2 = r - q; // size of right array

int L[] = new int[n1 + 1];// left array

int R[] = new int[n2 + 1]; //right array

for (int i = 0; i < n1; i++) // going through the first half

{

L[i] = a[p + i];

}

for (int j = 0; j < n2; j++) // going through the second half

{

R[j] = a[q + j + 1];

}

L[n1] = Integer. MAX_VALUE; //sentinel value

R[n2] = Integer. MAX_VALUE;

int i = 0;

int j = 0;

int k = p;

while(i
{

count++;

if (L[i] <= R[j])

{

a[k] = L[i];

i = i + 1;

}

else

{

a[k] = R[j];

j = j + 1;

}

k++;

}

while (i < n1)

{

a[k] = L[i];

i++;

k++;

}

while (j < n2)

{

a[k] = R[j];

j++;

k++;