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

We can rewrite the MERGE(A, p, q, r) as follows…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n1 = q - p + 1
n2 = r - q
create arrays L[1..n1] and R[1..n2]
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
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.