Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

Merge sort is a sorting technique based on divide and conquer technique.

Explanation:

MERGE (A, p, q, r)

n1 = q - p + 1

n2 = r - q

L[1 ... n1] and R[1 ... n2] this creates the new array

for i = 1 to n1

L[i] = A[p + i - 1]

for j = 1 to n2

R[j] = A[q + j]

i = 1

j = 1

for k = p to r

if i > n1

A[k] = R[j]

j = j + 1

else if j > n2

A[k] = L[i]

i = i + 1

else if L[i] ≤ R[j]

A[k] = L[i]

i = i + 1

else

A[k] = R[j]

j = j + 1