Exercise 2.3.2

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.

Here is a simple modification:

MERGE(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  let L[1..n₁] and R[1..n₂] be new arrays
  for i = 1 to n₁
      L[i] = A[p + i - 1]
  for j = 1 to n₂
      R[j] = A[q + j]
  i = 1
  j = 1
  for k = p to r
      if i > n₁
          A[k] = R[j]
          j = j + 1
      else if j > n₂
          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

C code

#include <stdio.h>

void merge(int A[], int p, int q, int r) {
    int i, j, k;

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (i = 0; i < n1; i++)
        L[i] = A[p + i];
    for (j = 0; j < n2; j++)
        R[j] = A[q + j + 1];

    for(i = 0, j = 0, k = p; k <= r; k++) {
        if (i == n1) {
            A[k] = R[j++];
        } else if (j == n2) {
            A[k] = L[i++];
        } else if (L[i] <= R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}

void merge_sort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}