Categories
interview

Merge Sort

Runtime Complexity: O(n*log(n))

const mergeSort = (arr, low, high) => {
  if (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);
    merge(arr, low, mid, high);
  }
};

const merge = (arr, low, mid, high) => {
  const tempArr = [];
  let i = low;
  let j = mid + 1;
  let k = 0;
  while (i <= mid && j <= high) {
    tempArr[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  }
  while (i <= mid) {
    tempArr[k++] = arr[i++];
  }
  while (j <= high) {
    tempArr[k++] = arr[j++];
  }
  for (const val of tempArr) {
    arr[low++] = val;
  }
};

const arr = [4, -1, 1, 0, 3, 4];
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]

Demo