算法协议:递归拆分与有序合并 | 复杂度:O(n log n)
1. 彻底分解 (Divide): 不断将阵列对半切开,直到每个小组只有一个元素(单兵作战)。
2. 有序重组 (Merge): 将两个有序的小组两两合并。每次挑两个小组中最小的那个“先入场”。
3. 稳定进化: 归并排序是“稳定的”,相同大小的元素在排序后相对位置保持不变。
async function mergeSort(arr, l, r) { if (l >= r) return; let m = Math.floor((l + r) / 2); await mergeSort(arr, l, m); // 拆分左半 await mergeSort(arr, m + 1, r);// 拆分右半 await merge(arr, l, m, r); // 融合 } // 合并逻辑的核心: while(i < n1 && j < n2) { if(L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; }