Categories
interview

Merge Sort

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

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

const merge = (arr, low, mid, high) => {
  const leftSize = mid - low + 1;
  const rightSize = high - mid; // i.e., high - (mid+1) + 1;
  const left = [];
  const right = [];
  for (let i = 0; i < leftSize; i++) {
    left[i] = arr[low + i];
  }
  for (let i = 0; i < rightSize; i++) {
    right[i] = arr[mid + 1 + i];
  }
  let i = 0;
  let j = 0;
  while (i < leftSize && j < rightSize) {
    arr[low++] = left[i] <= right[j] ? left[i++] : right[j++];
  }
  while (i < leftSize) {
    arr[low++] = left[i++];
  }
  while (j < rightSize) {
    arr[low++] = right[j++];
  }
};

const inp = [4, 3, 2, 1];
sort(inp, 0, 3);
console.log(inp);
// [1, 2, 3, 4]

Demo