归并排序（Merge Sort）是一种分治思想的排序算法。
它将一个大的数组分割成两个较小的子数组，分别对这两个子数组进行排序，然后将它们合并成一个有序的大数组。
以下是一个使用 JavaScript 实现的归并排序算法：
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
// 测试
const arr = [5, 3, 8, 4, 2];
console.log(mergeSort(arr));
在这个实现中，mergeSort 函数是递归的，它将数组分割成两半，直到数组的长度小于 2（即数组为空或只有一个元素，此时数组已经是有序的）。
然后，它使用 merge 函数将两个已排序的子数组合并成一个有序的大数组。
merge 函数通过比较两个子数组的第一个元素，将较小的元素添加到结果数组中，并从相应的子数组中删除该元素。
这个过程一直持续到其中一个子数组为空。然后，它将另一个子数组的剩余元素添加到结果数组中。
这个算法的时间复杂度是 O(n log n)，其中 n 是数组的长度。
这是因为每次递归调用都会将数组的大小减半，所以递归的深度是 log n。
在每一层递归中，我们都需要遍历整个数组来合并它，所以每一层的时间复杂度是 O(n)。因此，总的时间复杂度是 O(n log n)。
