在做 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++];  // 可以看出这是一个稳定的排序算法elsetemp[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) 不含 midR = 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 中的元素，将较小值放入 arrwhile i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# 若有剩余部分，都复制到 arr 中while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1if __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)。