/**
* @param list 排序列表
* @param startIndex 开始位置，一般从0开始
* @param endIndex 结束位置，这里不是结束的索引
* @returns 排序好的数组
* @example
* let arr = [5,4,1,3,2]
* // 注意endIndex 传的是数组的长度
* Mergesort(arr, 0, arr.length);
* console.log(arr);
*/
function Mergesort(list: number[], startIndex: number, endIndex: number) {
let length = Math.floor(endIndex - startIndex);
if (length <= 1) {
return;
} else if (length === 2) {
let left = list[0];
let right = list[1];
if (left > right) {
list[0] = right;
list[1] = left;
return;
}
}
let middleIndex = Math.floor((startIndex + endIndex) / 2);
Mergesort(list, startIndex, middleIndex);
Mergesort(list, middleIndex, endIndex);
const copyList = list.slice(0);
let leftIndex = startIndex;
let rightIndex = middleIndex;
let outputIndex = startIndex;
while (true) {
let left = copyList[leftIndex];
let right = 0;
if (rightIndex != endIndex) right = copyList[rightIndex];
let useLeft = left < right;
if (rightIndex === endIndex) useLeft = true;
else if (leftIndex === middleIndex) useLeft = false;
if (useLeft) list[outputIndex++] = copyList[leftIndex++];
else list[outputIndex++] = copyList[rightIndex++];
if (leftIndex === middleIndex && rightIndex === endIndex) break;
}
}
FYI: https://www.youtube.com/watch?v=fEjZrwDKdi8&list=PLW3Zl3wyJwWOpdhYedlD-yCB7WQoHf-My&index=30
