merge-sort.js

/*
split, compare and merge
first implement function to merge two sorted arrays O(n+m)
Complexity O(n log n)
*/
function sortAndMerge(listA, listB) {
  // O(n+m); n+m == sum of length of both arrays
  let shorter = listA.length > listB.length ? listB : listA;
  let longer = listA.length <= listB.length ? listB : listA;
  let result = [],
    iS = 0,
    iL = 0;

  while (iS < shorter.length && iL < longer.length) {
    if (shorter[iS] < longer[iL]) {
      result.push(shorter[iS]);
      iS++;
    }

    if (longer[iL] <= shorter[iS]) {
      result.push(longer[iL]);
      iL++;
    }
  }

  let iIncompleted = iL < longer.length ? iL : iS;
  let incompleted = iL < longer.length ? longer : shorter;

  while (iIncompleted < incompleted.length) {
    result.push(incompleted[iIncompleted]);
    iIncompleted++;
  }

  return result;
}

function sort(list) {
  if (list.length == 1) return list;

  const mid = Math.floor(list.length / 2);
  const left = sort(list.slice(0, mid));
  const right = sort(list.slice(mid));

  return sortAndMerge(left, right);
}

console.log(sort([1, 2, 3, 1, 2, 9, 0]));