41.implement-Merge-Sort.md

41. implement Merge Sort

Problem

https://bigfrontend.dev/problem/implement-Merge-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Merge Sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function mergeSort(arr) {
  mergeSortImpl(arr, 0, arr.length - 1);
}

function mergeSortImpl(arr, start, end) {
  if (start >= end) {
    return;
  }

  const mid = Math.floor((start + end) / 2);
  mergeSortImpl(arr, start, mid);
  mergeSortImpl(arr, mid + 1, end);
  merge(arr, start, mid, end);
}

function merge(arr, start, mid, end) {
  const lowHalf = [];
  const highHalf = [];

  let k = start;
  let i;
  let j;
  for (i = 0; k <= mid; i++, k++) {
    lowHalf[i] = arr[k];
  }

  for (j = 0; k <= end; j++, k++) {
    highHalf[j] = arr[k];
  }

  k = start;
  i = 0;
  j = 0;

  while (i < lowHalf.length && j < highHalf.length) {
    if (lowHalf[i] < highHalf[j]) {
      arr[k] = lowHalf[i];
      i++;
    } else {
      arr[k] = highHalf[j];
      j++;
    }
    k++;
  }

  while (i < lowHalf.length) {
    arr[k] = lowHalf[i];
    i++;
    k++;
  }

  while (j < highHalf.length) {
    arr[k] = highHalf[j];
    j++;
    k++;
  }
}