This solution is generated by ChatGPT, correctness is not guaranteed. You might also be able to find a solution fromcommunity posts.

# 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.