??在做 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(n2)）相比，首選歸并。

長度為 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)				 22 段
...			  ...
層 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 等語言內置為穩定排序的重要原因。

1. 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)。

2. 首先，歸并排序的空間復雜度為 O(n)，這個前面有提到。而 Timsort 最好、平均情況下，空間復雜度是 O(log n)，最壞情況下是 O(n)。所以 python 的內置 sort 函數空間復雜度與 Timsort 一樣，因為在算法分析里通常按最壞情況報，所以其空間復雜度嚴格來講是 O(n)。

??在實際使用中，尤其是面試或教科書中，Python 的 list.sort() 被視為原地排序，不額外暴露用戶層級的空間使用，因此常簡化為 O(1)。