Merge Sort

Size
Speed

Description

This algorithm works by recursively splitting the array in half until we reach sub arrays of only size 1.

Then merge these sub arrays in a sorted manner.

Keep merging the sub arrays in a sorted manner until we have a single sorted array.

Complexity

Time
  • Best Case
  • Worst Case
  • Average Case
  • O(nlogn)
  • O(nlogn)
  • O(nlogn)
Space
  • O(n)

Implementation

function merge(arr, l, m, r) {

  let n1 = m - l + 1;
  let n2 = r - m;

  let L = new Array(n1 + 1);
  let R = new Array(n2 + 1);

  for (let i = l; i <= m; i++) {
    L[i - l] = arr[i];
  }

  for (let i = m + 1; i <= r; i++) {
    R[i - (m + 1)] = arr[i];
  }

  L[n1] = Infinity;
  R[n2] = Infinity;

  let i = 0;
  let j = 0;

  for (let k = l; k <= r; k++) {
    if (L[i] < R[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = R[j];
      j++;
    }
  }

}


function mergeSort(arr, l, r) {

  if (l < r) {
    let m = Math.floor((l + r) / 2);
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }

}