function mergeSort(arr, left, right) {
if (left < right) {
let mid = Math.floor((left + right) / 2);
mergeSort(arr, left, mid); // 递归排序左半部分
mergeSort(arr, mid + 1, right); // 递归排序右半部分
merge(arr, left, mid, right); // 合并两个有序数组
}
}
function merge(arr, left, mid, right) {
let temp = [];
let i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i]); i++;
} else {
temp.push(arr[j]); j++;
}
}
while (i <= mid) { temp.push(arr[i]); i++; }
while (j <= right) { temp.push(arr[j]); j++; }
for (let k = left; k <= right; k++) {
arr[k] = temp[k - left];
}
}