Merge Sort

Merge sort is a Divide & Conquer algorithm. It divides the input array into 2 halves, and recursively breaks those halves until they become so small that it can’t be broken further. Then, each section of the pieces are merged together to inch towards the final answer.

                    [30, 20, 40, 10, 80, 50, 15]
                  /                             \
        [30, 20, 40, 10]                      [80, 50, 15]
        /             \                       /          \
  [30, 20]          [40, 10]               [80,50]       [15]
  /      \          /      \               /     \         \
[30]    [20]      [40]    [10]           [80]   [50]       [15]
  \      /          \      /               \     /          /
  [20, 30]          [10, 40]               [50,80]        [15]
        \            /                          \         /
        [10, 20, 30, 40]                       [15, 50, 80]
                      \                         /
                      [10, 15, 20, 30, 40, 50, 60]

Code algorithm

Let’s now look at how to implement it in code.

function mergeSort(arr: number[], left: number, right: number): void {
  if (right > left) {
    const mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
  }
}

function merge(arr: number[], left: number, mid: number, right: number): void {
  const leftTmp = new Array(mid - left + 2);
  const rightTmp = new Array(right - mid + 1);

  for (let i = 0; i < mid - left + 1; ++i) {
    leftTmp[i] = arr[left + i];
  }

  for (let i = 0; i < right - mid; ++i) {
    rightTmp[i] = arr[mid + 1 + i];
  }

  leftTmp[mid - left + 1] = Number.MAX_SAFE_INTEGER;
  rightTmp[right - mid] = Number.MAX_SAFE_INTEGER;

  let i = 0;
  let j = 0;

  for (let k = left; k < right + 1; ++k) {
    if (leftTmp[i] < rightTmp[j]) {
      arr[k] = leftTmp[i];
      i += 1;
    } else {
      arr[k] = rightTmp[j];
      j += 1;
    }
  }
}

For time and space complexity, check out my post on Run Time Complexity.