Merge Sort

• Merge sort divides the array into two halves, recursively sorts each half, and then merges them back together in sorted order.

• It follows the divide-and-conquer approach, achieving a time complexity of O(nlogn).

Code

function mergeSort(arr) {
  const length = arr.length;

  if (length <= 1) {
    return arr;
  }

  const mid = Math.floor(length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

function merge(leftArr, rightArr) {
  const sortedArr = [];

  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr.shift());
    } else {
      sortedArr.push(rightArr.shift());
    }
  }

  return [...sortedArr, ...leftArr, ...rightArr];
}

console.log(mergeSort([6, 5, 12, 10, 9, 1]));