AI solution for JavaScript Coding Question on BFE.dev
41. implement Merge Sort

Solution:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return;
  }
  const middle = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, middle);
  const rightArr = arr.slice(middle);
  mergeSort(leftArr);
  mergeSort(rightArr);
  merge(arr, leftArr, rightArr);
}

function merge(arr, leftArr, rightArr) {
  let i = 0;
  let j = 0;
  let k = 0;
  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k++] = leftArr[i++];
    } else {
      arr[k++] = rightArr[j++];
    }
  }
  while (i < leftArr.length) {
    arr[k++] = leftArr[i++];
  }
  while (j < rightArr.length) {
    arr[k++] = rightArr[j++];
  }
}

const arr = [3,7,8,5,2,1,9,5,4];
mergeSort(arr);
console.log(arr); // Output: [1, 2, 3, 4, 5, 5, 7, 8, 9]

Time complexity of merge sort in the worst case is O(n*log(n)). It is a stable sorting algorithm as order of equal elements is not changed during sorting.