归并排序（Merge Sort）是一种分而治之的算法，它将数组分成两半，对每半部分递归地应用归并排序，然后将排序好的两半合并在一起。JavaScript 中实现归并排序的步骤如下：
分解：将数组分解成两个较小的子数组，直到子数组的大小为1。
递归进行排序并合并：递归地对子数组进行排序，并将已排序的子数组合并成一个大的有序数组，直到合并为1个完整的数组。
以下是 JavaScript 中归并排序的一个简单实现：
class MergeSort<T> {
// 合并两个数组
merge(leftArr: T[], rightArr: T[]) {
let leftIndex = 0;
let rightIndex = 0;
let result: T[] = [];
while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
if (leftArr[leftIndex] <= rightArr[rightIndex]) {
result.push(leftArr[leftIndex]);
leftIndex++;
} else {
result.push(rightArr[rightIndex]);
rightIndex++;
}
}
while (leftIndex < leftArr.length) {
result.push(leftArr[leftIndex]);
leftIndex++;
}
while (rightIndex < rightArr.length) {
result.push(rightArr[rightIndex]);
rightIndex++;
}
return result;
}
// 排序：二分法先拆分， 再合并
sortBySplit(arr: T[]): T[] {
if (arr.length <= 1) {
return arr;
}
let middleIndex = Math.floor(arr.length / 2);
let leftArr = arr.slice(0, middleIndex);
let rightArr = arr.slice(middleIndex);
return this.merge(this.sortBySplit(leftArr), this.sortBySplit(rightArr));
}
}
const mergeSortTest = new MergeSort<number | string>();
console.log(mergeSortTest.sortBySplit([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])); // [ 1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9 ]
