mergeSort
归并排序 - 经典的分治排序算法,稳定排序。
输入数组
执行过程
开始归并排序
左半部分
右半部分
合并结果
算法说明
归并排序采用分治法：分割数组，递归排序左右两半，然后合并。稳定排序，时间复杂度O(n log n)，空间复杂度O(n)。
函数签名
typescript
function mergeSort(arr: number[]): number[]
function mergeSortInPlace(arr: number[]): number[]参数
| 参数名 | 类型 | 必填 | 说明 |
|---|---|---|---|
arr | number[] | 是 | 待排序数组 |
返回值
| 类型 | 说明 |
|---|---|
number[] | 排序后的数组 |
工作原理
- 分割: 将数组分成两半
- 递归排序: 分别对左右两半进行归并排序
- 合并: 将两个已排序的数组合并成一个
- 终止条件: 数组长度≤1时直接返回
合并过程:
- 使用双指针遍历两个数组
- 每次选择较小的元素加入结果
- 将剩余元素依次加入
时间复杂度: O(n log n)
空间复杂度: O(n)
特点: 稳定排序,适合外部排序