在做 280. 摆动排序 时，有一版 python 题解，里面直接用了sort() ，又用了一个简单的 for 循环，但整体时间复杂度为 O(n⋅log(n)) ，那么问题就出自这个 sort() ，所以在这分析一下 sort() 的复杂度。
Python 的 list.sort() 用的是 TimSort 算法，而 TimSort 是一个稳定的混合排序算法，结合了归并排序和插入排序的优点。
那么在最坏情况下， sort() 函数的时间复杂度为什么是 O(n⋅log(n)) 呢？
前面提到 sort() 用的就是 TimSort 算法，而 TimSort 本质上是一种归并排序。最坏的情况下，数据完全无序，此时 TimSort 会退化为标准的归并排序。而归并排序的时间复杂度是 O(n⋅log(n))。
先大概总结下归并排序的算法复杂度由来：
- 分解：将长为 n 的列表递归地分成两半，这会形成一个深度为 log(n) 的递归树。 → 把规模减半，产生 log n 层递归。
- 合并：每层递归中，均需将两个已排序的子列表合并成一个，这个过程需要遍历所有元素，因此每层的时间复杂度是 O(n)。 → 每层都要做一次线性合并，每层代价 O(n)。
两者相乘，得到总的时间复杂度为 O(n⋅log(n))。
来个例子：
数组 A = [38, 27, 43, 3, 9, 82, 10]
1. 分解
递归地把数组对半劈开，直到只剩单个元素（天然有序）：
[38 27 43 3 | 9 82 10]
[38 27 | 43 3] ...
...
[38] [27] [43] [3] [9] [82] [10]
2. 合并
自底向上把“已排好序的两段”归并成更长的一段。
合并 [38] 与 [27] → [27 38]
合并 [43] 与 [3] → [3 43]
合并 [27 38] 与 [3 43] → [3 27 38 43]
右侧同理 → [9 10 82]
最后把 [3 27 38 43] 与 [9 10 82] 合并 → [3 9 10 27 38 43 82]
现在仔细分析一下，归并排序的核心思想就是 —— 先把左半边排好，再把右半边排好，最后把两个已排好的部分合并。代码如下：
// JAVA
public class MergeSort{
public static void sort(int[] array) {
if(array == null || array.length == 0){
return;
}
mergerSort(array, 0, array.length - 1);
}
// 递归
private static void mergeSort(int[] array, int left, int right) {
if(left < right){
int mid = left + (left + right) / 2;
// 递归排序左半部分
mergeSort(array, left, mid);
// 递归排序右半部分
mergeSort(array, mid + 1, right);
// 合并 2 个已排序的部分（归并）
merge(array, left, mid, right);
}
}
// 合并 2 个已排序的部分（将前后两个相邻有序表归并成一个有序表）
private static void merge(int[] array, int left, int mid, int right){
// 创建临时数组存储合并后的结果，所以空间复杂度为 O(n)
// 若用 C，可 malloc 申请，注意格式 ElemType *B = (ElemType *)malloc(n*sizeof(ElemType));
int[] temp = new int[right - left +1];
int i = left; // 左半部分的起始索引
int j = mid + 1; // 右半部分的起始索引
int k = 0; // 临时数组的当前索引
// 将 2 个部分的元素按顺序复制到临时数组
while (i <= mid && j <= right){
if (array[i] <= array[j])
temp[k++] = array[i++]; // 可以看出这是一个稳定的排序算法
else
temp[k++] = array[j++];
}
// 若有剩余部分，都复制到临时数组
while(i <= mid) temp[k++] = array[i++]; // 第1个表未检测完
while(j <= right) temp[k++] = array[j++]; // 第2个表未检测完
// 将排序后的元素从临时数组复制回原数组中
for (k = 0; k < temp.length; k++) {
array[left + k] = temp[k];
}
}
// 测试归并排序函数
public static void main(String[] args) {
int[] array = {38, 27, 43, 3, 9, 82, 10};
sort(array); // 调用归并排序函数
for (int value : array){
System.out.print(value + " ");
}
}
}
# python
def merge_sort(arr):
"""
归并排序函数
arr: 待排序列表
"""
if len(arr) > 1:
mid = len(arr) // 2 # 除后向下取整，找到中间索引
L = arr[:mid] # 左半部分[0, mid) 不含 mid
R = arr[mid:] # 右半部分[mid, len(arr)-1]含 mid
# 递归排序
merge_sort(L)
merge_sort(R)
merge(arr, L, R) # 合并两个有序子列表
def merge(arr, L, R):
"""
合并两个已排序子列表到原数组 arr
arr: 原始数组（最终有序）
L: 左子列表（已排序）
R: 右子列表（已排序）
"""
i = j = k = 0
# 逐一比较 left 和 right 中的元素，将较小值放入 arr
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 若有剩余部分，都复制到 arr 中
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
if __name__ == "__main__":
nums = [38, 27, 43, 3, 9, 82, 10]
print("排序前：", nums)
merge_sort(nums)
print("排序后", nums)
注意：
Python 切片 arr[:mid]、arr[mid:] 会创建新的列表对象，而非对原数组做“视图”或指针操作。merge_sort 的每一次递归调用里，都额外复制出两个子列表：
L = arr[:mid]
R = arr[mid:]
这些临时列表占用的空间总和在最底层达到 O(n)，再加上递归栈的 O(log n)，整体空间复杂度就是 O(n)。
所以，看起来是原地归并（对原始 arr 直接操作），但实际上产生了额外的空间占用。
那么，下面我们来研究一下这个递归栈。
前面说了，归并排序的时间复杂度为 O(n log n)，且 最坏 / 平均 / 最好 三种情况都是这个量级。
所以若是内存允许（归并空间O(n)，快排空间 O(log n)），只考虑时间复杂度，则与快排（平均 O(n log n)，最坏O(n²)）相比，首选归并。
长度为 n 的列表，完成归并排序所需的基本操作次数，设为 T(n)。
merge 阶段把两个已排好序的子序列合并成一个，需要逐元素扫描一次，时间复杂度为 O(n)。
所以完成归并，总的基本操作次数为
T(1) = O(1)
T(n) = 2T(n/2) + O(n) (n >= 2)
2·T(n/2)：把 n 个元素分成左右两半，各递归排序一次。
递归树的大致结构如下：
层 0： n (merge 合并开销 n) 1 段
层 1： n/2 n/2 (每段合并开销 n/2+n/2 = n) 2 段
层 2： n/4 n/4 n/4 n/4 (合并开销还是 n) 2² 段
... ...
层 k： 每段长度 n/2^k，共 2^k 段，合并总开销仍是 n 2^k 段
树高 h = log₂ n ，每层合并开销都是 n，因此总时间：T(n) = n · log₂ n = O(n log n)
归并排序的切分点固定在中间，与输入数据分布无关；合并阶段总是线性扫描。因此，最坏 / 平均 / 最好情况的时间复杂度完全一致，都是 O(n log n)。
比较次数 ≈ n log₂ n − n + 1（可忽略低阶项）。
额外复制：每次 merge 都线性复制一次，但只影响空间，不影响时间复杂度。
空间上：
每次进 merge_sort(arr)，递归栈也就是调用栈里主要保存：
- 局部变量 mid
- 两个新列表：left, right（切片生成，长度之和≈n）
- 返回地址、当前代码行号等解释器内部信息
2 个子列表本身是在堆上分配的，但它们的 引用 存在栈里，所以每递归 1 次，要额外消耗 O(n) 的堆空间；而栈本身只存引用和少量标量 ，因此单个帧的栈空间占用是常数级。
再看递归深度：归并排序每次把区间折半，因此递归深度是 depth_max = ⌊log₂ n⌋ + 1
递归栈空间总量：
- 栈空间：只存每层的一个常数大小的帧，因此总量是 O(depth_max) = O(log n)
- 堆空间：由于每层都复制子列表，且同一时刻，最多仅 1 条从根到叶子的路径上，存在各层副本，因此最大同时占用的堆空间是 n + n/2 + n/4 + … ≈ 2n = O(n)
这就是 归并排序 的空间复杂度 O(n) 的来源。
归并排序在任何情况下，时间上都稳定运行在 O(n log n)，无退化风险，这也是它被 Python、Java 等语言内置为稳定排序的重要原因。
- python 的内置 sort 函数底层基于 Timsort 算法，而 Timsort 算法本质上是一种归并排序，所以时间复杂度为 O(n log n)
- 最坏情况下， Timsort 算法时间复杂度为 O(n log n)。
- 最好情况下，即全局有序 or 接近有序时，Timsort 算法只线性扫描一次，无需归并，时间复杂度为 O(n)。
- 平均情况下，Timsort 算法需要 log n 级别的归并层数，与经典归并和快排持平，时间复杂度为 O(n log n)。
综上，sort 函数时间复杂度为 O(n log n)。
- 首先，归并排序的空间复杂度为 O(n)，这个前面有提到。而 Timsort 最好、平均情况下，空间复杂度是 O(log n)，最坏情况下是 O(n)。所以 python 的内置 sort 函数空间复杂度与 Timsort 一样，因为在算法分析里通常按最坏情况报，所以其空间复杂度严格来讲是 O(n)。
在实际使用中，尤其是面试或教科书中，Python 的 list.sort() 被视为原地排序，不额外暴露用户层级的空间使用，因此常简化为 O(1)。