Merge Sort

Overview

Property	Value
Best Case	$\Omega (n\lg n)$
Worst Case	$O(n\lg n)$
Avg. Case	$O(n\lg n)$
Aux. Memory	$O(n)$
Stable	-
Adaptive	-

static void merge(int i, int mid, int j, int *A) {
  int si = mid - i + 1;
  int sj = j - (mid + 1) + 1;
 
  int *L = malloc(sizeof(int) * (si + 1));
  int *R = malloc(sizeof(int) * (sj + 1));
 
  L[si] = INT_MAX;
  R[sj] = INT_MAX;
 
  for (int k = 0; k < si; ++k) {
    L[k] = A[i + k];
  }
  for (int k = 0; k < sj; ++k) {
    R[k] = A[mid + 1 + k];
  }
 
  int topL = 0, topR = 0;
  for (int k = 0; k < j - i + 1; ++k) {
    if (L[topL] < R[topR]) {
      A[i + k] = L[topL++];
    } else {
      A[i + k] = R[topR++];
    }
  }
 
  free(L);
  free(R);
}
 
void merge_sort(int i, int j, int *A) {
  if (j <= i) {
    return;
  }
  int mid = (i + j) / 2;
  merge_sort(i, mid, A);
  merge_sort(mid + 1, j, A);
  merge(i, mid, j, A);
}

Bibliography

• Thomas H. Cormen et al., Introduction to Algorithms, Fourth edition (Cambridge, Massachusett: The MIT Press, 2022).