1. 歸并排序到底在做什么分治思想與執(zhí)行流程歸并排序是被討論最多但也是最容易被輕視的經典排序之一。它的平均時間復雜度穩(wěn)定在 O(nlog2n)無論輸入是剛好亂序還是接近有序這個上界都不會變。很多人能背出遞歸代碼卻說不清為什么需要臨時數組、為什么先遞歸再合并、為什么合并過程一定要雙指針。這篇文章想把歸并排序從思想層到代碼層徹底拆開先講它到底在做什么再推導 O(nlog2n) 的來源然后給出可直接復用的遞歸版和迭代版實現最后聊工程落地時真正值得注意的坑和優(yōu)化。適合讀這篇內容的人有兩類一類是準備技術面試的開發(fā)者歸并排序幾乎是必考點而且經常衍生出逆序對、鏈表排序、外部排序等問題另一類是工作中要寫數據處理工具的工程師需要在大數據量排序時選對算法。文章里的代碼我以 Python 為主但思路可以平移到任何語言。1.1 分治思想拆解不是“把一個數組拆開”這么簡單分治策略有三個動作分解、解決、合并。歸并排序對這三個動作的執(zhí)行順序非常明確先遞歸地把數組分成兩半直到每個子數組只剩一個元素然后開始逐步合并合并過程中完成排序。這里很多人有一個誤區(qū)以為歸并排序的核心是“拆分”。其實拆分只是輔助手段真正的排序發(fā)生在合并階段。把一個數組拆到只剩一個元素時每個子數組天然有序因為單個元素不需要比較。接下來要做的就是把兩個已經各自有序的數組按照大小關系合并成一個新的有序數組。這種“把無序數組變成若干有序片段再通過有序片段合并得到整體有序”的思路才是歸并排序區(qū)別于冒泡、選擇這些暴力排序的本質。另一個容易混淆的點歸并排序和快速排序都用了分治但方向是相反的?？炫攀窃诜謪^(qū)之后就對數據做了調整使得基準值左邊的數據都小于等于它、右邊的數據都大于等于它然后遞歸處理左右兩邊而歸并排序先遞歸到底排序實際發(fā)生在“歸”回來的路上。這也是為什么歸并排序在合并時需要輔助空間而快排可以在原數組上通過交換完成分區(qū)。1.2 合并兩個有序數組整個算法的靈魂假設你有兩個已經排好序的數組比如 [1, 3, 5] 和 [2, 4, 6]要把它們合并成一個有序數組最自然的做法是雙指針一個指針指向左數組開頭一個指針指向右數組開頭每次比較兩個指針指向的元素較小的放入結果數組然后對應指針后移。如果某一方先走完就把另一方的剩余元素直接接到結果后面。這個過程看起來簡單但它決定了歸并排序的穩(wěn)定性。如果我們比較的時候使用arr[i] arr[j]而不是那么兩個相等的元素會優(yōu)先取左邊的這樣在合并過程中不會破壞相同元素的原始相對順序。穩(wěn)定性在業(yè)務場景里非常關鍵比如先按時間排序、再按優(yōu)先級排序如果第二次排序是不穩(wěn)定的第一次排序的順序就白做了。合并兩個有序數組的操作就是 merge。整個歸并排序的執(zhí)行過程可以理解成無數個 merge 嵌套在一起最小規(guī)模是兩個長度為 1 的數組合并成長度為 2 的有序數組然后兩個長度為 2 的數組合并成長度為 4 的有序數組一層一層向上直到最后兩個長度為 n/2 的數組被合并成完整的 n 長度數組。1.3 手動模擬一趟完整合并建立遞歸直覺用經典的數組 [38, 27, 43, 3, 9, 82, 10] 走一遍。先按中點拆分成 [38, 27, 43, 3] 和 [9, 82, 10]左半部分繼續(xù)拆成 [38, 27] 和 [43, 3]再拆成 [38]、[27]、[43]、[3]。從最底層開始合并[38] 和 [27] 合并成 [27, 38][43] 和 [3] 合并成 [3, 43]然后這兩個有序數組再合并成 [3, 27, 38, 43]。另一邊也做同樣的事情[9, 82, 10] 拆成 [9]、[82]、[10]合并后得到 [9, 10, 82]。最后兩個有序數組 [3, 27, 38, 43] 和 [9, 10, 82] 雙指針合并得到 [3, 9, 10, 27, 38, 43, 82]排序完成。注意整個過程的執(zhí)行順序是深度優(yōu)先的先一路拆到最左邊的最底層完成合并再回來處理右邊的分支。這也是遞歸程序的特點理解這一點后寫代碼時就不會糾結為什么合并函數要在兩次遞歸調用之后才執(zhí)行。2. O(nlog2n) 是怎么算出來的復雜度推導與直覺2.1 從遞推公式到遞歸樹假設輸入規(guī)模為 n歸并排序把問題拆成兩個大小為 n/2 的子問題每個子問題的代價是 T(n/2)合并兩個有序子數組需要掃描所有 n 個元素代價是 O(n)。于是可以得到遞推式T(n) 2T(n/2) O(n)邊界條件是 T(1) O(1)因為單個元素不需要任何比較。把遞推式一層層展開T(n) 2T(n/2) n 2(2T(n/4) n/2) n 4T(n/4) 2n 8T(n/8) 3n ... (2^k)T(n/2^k) k*n當遞歸到達底層時n/2^k 1也就是 k log2n。代入后得到 T(n) n*T(1) log2n * n O(nlog2n)。這個推導過程建議親手寫一遍。很多面試里問“歸并排序為什么是 O(nlog2n)”本質上考的不是你能不能背出結論而是能不能從遞推式出發(fā)解釋層數和每層代價。遞歸樹法和這個展開是等價的樹的高度是 log2n每一層所有子問題加起來都要處理 n 個數據所以總代價是 n 乘以樹高。2.2 層數為什么是 log2n一個生活化類比可以把歸并排序想象成一個班級廣播通知的下發(fā)過程一個老師告訴兩位班長兩位班長各自告訴四位組長四位組長再告訴八位組員。每次信息傳遞量翻倍從 1 到 n需要的層數就是從 n 除以 2 一直到 1 的除法次數也就是 log2n。歸并排序的遞歸樹高度正好是這樣的對數結構。每層合并代價都是 O(n) 這一點也值得展開。第 0 層只有一次合并掃描 n 個元素第 1 層有兩次合并每次掃描 n/2 個元素加總還是 n第 2 層有四次合并每次掃描 n/4 個元素加總依然是 n。無論哪一層所有合并操作的總掃描長度都是 n。這個規(guī)律貫穿整個算法所以復雜度就是“層數乘以每層代價”即 log2n 乘以 n。說到這里必須提醒一點O(nlog2n) 是平均時間復雜度同時也是最好和最壞時間復雜度。歸并排序不會因為輸入已經有序而減少比較次數也不會因為輸入完全逆序而增加比較次數。這一點和插入排序形成鮮明對比插入排序的最好情況只有 O(n)。歸并排序的這種確定性在實時性要求高的場景里是優(yōu)勢在追求極致性能的緩存場景里也可能成為劣勢這點后續(xù)會展開。2.3 空間復雜度與穩(wěn)定性為什么臨時數組是剛需歸并排序的空間復雜度是 O(n)因為每次合并兩個有序數組時需要一個和整體規(guī)模等長的臨時數組來存放結果。遞歸調用本身的棧深度是 log2n所以如果嚴格計算總空間占用是 O(n) 加上 O(log2n) 的函數棧但 O(log2n) 被 O(n) 主導通常就記作 O(n)。很多人會問能不能不用臨時數組在原數組上直接完成歸并如果嚴格要求原地也可以做但要么用復雜的原地旋轉算法把時間復雜度推到 O(nlog2n) 上方要么犧牲排序穩(wěn)定性工程上都不劃算。一個更常見的做法是預先分配一個長度為 n 的臨時數組在遞歸過程中反復使用它而不是每次 merge 都新建數組。這樣空間開銷只是 O(n)不會變成 O(nlog2n)。穩(wěn)定性來源于合并時對相等元素的處理。如果寫成if arr[i] arr[j]相等的時候先取左半部分那么原始順序就被保留了。如果寫成相等時先取右半部分穩(wěn)定性就被破壞。很多初寫歸并排序的人在這里不小心寫錯導致排序結果正確但“穩(wěn)定排序”的名頭丟了。3. 遞歸版與迭代版完整實現代碼是最快的說明書3.1 遞歸實現的正確姿勢遞歸版歸并排序的代碼結構非常固定外層是排序函數內層是合并函數。一個容易踩的坑是臨時數組的處理。不要在遞歸函數內部反復創(chuàng)建數組正確的做法是在入口函數里一次性創(chuàng)建好然后作為參數向下傳遞。def merge(arr, left, mid, right, temp): i, j, k left, mid 1, left while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 for t in range(left, right 1): arr[t] temp[t] def merge_sort_recursive(arr, left, right, temp): if left right: return mid left (right - left) // 2 merge_sort_recursive(arr, left, mid, temp) merge_sort_recursive(arr, mid 1, right, temp) merge(arr, left, mid, right, temp) def merge_sort(arr): temp [0] * len(arr) merge_sort_recursive(arr, 0, len(arr) - 1, temp)注意兩點mid left (right - left) // 2而不是(left right) // 2后者在極端情況下可能產生整數溢出雖然 Python 的整數不會溢出但其他語言需要養(yǎng)成這個習慣。另外合并結束后要把臨時數組拷貝回原數組。這里用的是循環(huán)拷貝如果是在 Python 里也可以直接用切片arr[left:right1] temp[left:right1]但循環(huán)更便于理解也避免了切片帶來的額外對象開銷。3.2 自底向上的迭代實現遞歸實現的缺點是當數組規(guī)模特別大時遞歸深度會達到 log2n雖然不容易爆棧但在某些嵌入式環(huán)境或函數棧極小的環(huán)境里仍然不放心。迭代版自底向上實現完全避開遞歸方法是從合并長度為 1 的子數組開始循環(huán)處理長度為 2、4、8 直到整個數組。def merge_sort_iter(arr): n len(arr) if n 2: return arr temp [0] * n width 1 while width n: left 0 while left n: mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: merge(arr, left, mid, right, temp) left 2 * width width * 2 return arr這里的 merge 函數和遞歸版共用。迭代版的核心是width每次翻倍left 每次前進2 * width保證當前合并的兩個區(qū)間分別是 [left, mid] 和 [mid1, right]。當數組長度不是 2 的冪時需要借助min對 mid 和 right 做鉗制。if mid right這個判斷很重要如果不加當左區(qū)間已經包含數組剩余全部元素時合并會去訪問一個不存在的右區(qū)間。3.3 兩種寫法在工程上如何取舍遞歸版更符合分治思想代碼可讀性好調試的時候可以用調用棧直觀看到分解過程。迭代版代碼稍顯繁瑣但避免了遞歸調用開銷在數據規(guī)模極大時更穩(wěn)。我個人的習慣是日常業(yè)務代碼用遞歸版因為邏輯清楚、不易出錯底層工具或需要極致穩(wěn)定性的場景用迭代版。下表簡單對比兩種實現的差異維度遞歸版迭代版代碼可讀性高和思想一一對應低需要理解 width 和 left 的推進關系函數調用開銷有但影響通?？珊雎詿o遞歸純循環(huán)?？臻g壓力需要 O(log2n) 遞歸棧幾乎不需要額外棧邊界處理難度較簡單需要小心鉗制 mid 和 right適用場景面試、業(yè)務排序、教學嵌入式環(huán)境、超大數組、無遞歸環(huán)境4. 工程落地避坑指南邊界、內存與微優(yōu)化4.1 最容易被忽略的邊界條件歸并排序寫錯的原因通常不是算法思想不對而是邊界處理不到位。第一個高頻錯誤是遞歸終止條件寫成left right這本身也能工作但會多一層無意義的遞歸更規(guī)范的是left right。第二個高頻錯誤是對mid的劃分。假設數組下標是 [left, right]左區(qū)間應該是 [left, mid]右區(qū)間是 [mid1, right]。如果錯誤地把右區(qū)間寫成 [mid, right]左區(qū)間會多一個元素最終排序結果雖然可能正確但會讓兩個區(qū)間不均衡破壞了歸并排序的分治邏輯甚至可能導致死循環(huán)。而且 mid 的計算方式必須和迭代版的鉗制邏輯一致否則左右區(qū)間會出現重疊或漏掉元素。第三個錯誤出現在合并后的拷貝階段。有些人只把臨時數組的一部分拷回原數組比如從 0 開始拷到 right-left卻沒有考慮 left 的偏移量。當 left 不是 0 時這種寫法會污染原數組里不屬于當前合并范圍的元素。正確的做法是從 left 開始循環(huán)到 right把 temp 對應位置拷回去。4.2 臨時數組分配策略統(tǒng)一分配還是每次創(chuàng)建很多初學版本的代碼長這樣在 merge 函數內部temp [0] * (right - left 1)看起來沒錯但每次遞歸調用都要重新分配數組整體空間分配次數等于合并次數約為 n 次量級。對于十萬元素或許還能忍受對于百萬千萬級數據創(chuàng)建大量臨時對象不僅耗時還容易觸發(fā)內存碎片。工程上的標準做法是在入口函數里一次性分配temp [0] * n之后所有遞歸層級共用這一塊空間。這是因為每次合并只需要訪問當前區(qū)間對應的位置不同分支遞歸并不會同時使用 temp 數組所以不存在數據覆蓋問題。這種方法把動態(tài)內存分配從 O(n) 次降低到常數次效果非常明顯。4.3 三個值得做的微優(yōu)化第一個優(yōu)化是小區(qū)間切換插入排序。當待排序區(qū)間長度小于某個閾值常用 16 或 32時不再繼續(xù)拆分和合并而是直接對小區(qū)間做插入排序。插入排序在規(guī)模小的時候常數因子遠小于歸并排序而且緩存友好。這個優(yōu)化是很多工業(yè)級排序庫的基礎做法。def merge_sort_optimized(arr, left, right, temp): if right - left 16: insertion_sort(arr, left, right) return mid left (right - left) // 2 merge_sort_optimized(arr, left, mid, temp) merge_sort_optimized(arr, mid 1, right, temp) if arr[mid] arr[mid 1]: return merge(arr, left, mid, right, temp)第二個優(yōu)化是判斷是否真的需要合并。如果左區(qū)間最后一個元素已經小于等于右區(qū)間第一個元素說明兩個區(qū)間已經天然有序整段不需要做任何操作。這個判斷只需要 O(1) 時間卻能在處理近似有序數組時跳過大量合并直接把最好情況的時間復雜度從 O(nlog2n) 降到 O(n)。它和插入排序的近似有序友好特性殊途同歸。第三個優(yōu)化是減少元素的重復拷貝。標準寫法每次合并完都把 temp 拷回 arr下一層合并又把 arr 拷到 temp。如果交替使用 arr 和 temp 作為目標數組可以讓數據在兩層之間直接往返省掉一部分拷貝。實現起來要復雜一些性能提升通常在 10% 到 20% 之間適合對性能有極致要求的讀者自己去研究業(yè)務場景不一定需要。4.4 常見錯誤與排查思路如果排序結果只是部分有序先檢查合并后拷貝的區(qū)間是否完整。如果數組完全沒排序檢查遞歸調用時 mid 的左右區(qū)間是否寫反。如果出現越界異常檢查 while 循環(huán)的終止條件是否寫成i mid而不是i mid。這些錯誤在調試時不一定要看完整數組可以用小規(guī)模隨機數組反復跑再對比 Python 內置的sorted()結果很快能定位。另一個實用技巧是在合并函數入口加一個斷言assert left mid right確保調用 merge 時區(qū)間參數合法。很多問題不是算法問題而是調用方沒有正確傳入區(qū)間范圍。加斷言后測試階段就能暴露問題而不是等線上數據出錯。5. 歸并排序的經典變體與應用場景5.1 逆序對統(tǒng)計merge 時的天然能力逆序對定義是如果 i j 且 arr[i] arr[j]這一對元素就是一個逆序對。暴力解法雙重循環(huán)需要 O(n2) 時間而歸并排序可以在合并過程中順手統(tǒng)計時間復雜度降到 O(nlog2n)。原理其實很巧妙。合并兩個有序子數組時當右區(qū)間的當前元素arr[j]小于左區(qū)間的當前元素arr[i]說明從 i 到 mid 的所有元素都大于arr[j]它們每一個都和arr[j]構成逆序對。此時一次性累加mid - i 1個逆序對而不是一個個比較。def merge_count(arr, left, mid, right, temp): i, j, k left, mid 1, left inv 0 while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 inv mid - i 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 for t in range(left, right 1): arr[t] temp[t] return inv這個寫法注意一點只有arr[i] arr[j]時才計數等于的情況不計。因為等于不是逆序對用取左區(qū)間元素可以保證穩(wěn)定性也不會多算逆序對。面試中經常把它作為歸并排序的進階題理解了這一行計數邏輯就掌握了一套高頻解題思路。5.2 外部排序與多路歸并如果數據量遠超內存比如幾十 GB 的日志文件要在內存只有幾個 GB 的機器上排序普通快排或者歸并都不能一次性完成。這時會用到外部排序而外部排序的核心就是把歸并排序的思路放大到文件級別。基本流程是把大文件切分成多個可讀入內存的塊每塊讀入內存后用快排或歸并排好序寫回磁盤形成多個臨時有序文件最后對這些有序文件做多路歸并。多路歸并不能簡單兩個文件兩兩合并因為那樣會產生大量磁盤 IO工程上一般用優(yōu)先隊列維護 k 個文件的最小元素每次取最小寫回輸出文件同時從對應文件補一個元素進來。這個過程本質上是 k 路歸并。之所以還是叫“歸并”是因為它和內存歸并排序共享同一個核心操作合并多個有序序列。區(qū)別只在于數據載體是文件以及為了減少磁盤 IO 引入的緩沖區(qū)設計?？梢哉f如果不理解歸并排序外部排序就很難展開這也是為什么很多大數據工程師會回頭補排序算法的底層知識。5.3 鏈表排序歸并排序的真正主場數組排序時歸并排序需要 O(n) 額外空間這是它對比快排的最大劣勢。但如果是鏈表排序歸并排序不需要額外開辟存儲空間因為鏈表節(jié)點之間的指針可以在合并時重新連接不需要新的節(jié)點數組。額外開銷只有遞歸函數棧 O(log2n)這比數組歸并要好得多。鏈表歸并的核心思路用快慢指針找到鏈表中點切成左右兩條鏈表遞歸排序后再用雙指針合并兩條有序鏈表。找中點的代碼我經?？吹接腥藢戝edef merge_sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next right_head merge_sort_list(slow.next) slow.next None left_head merge_sort_list(head) return merge_two_lists(left_head, right_head)這里 fast 從head.next開始走可以讓 slow 恰好停在左半部分的最后一個節(jié)點。如果 fast 也從 head 開始slow 可能會停在偏右的位置拆分就不準了。合并兩條有序鏈表的函數則是典型的雙哨兵節(jié)點技巧這里不再展開。5.4 與主流排序庫的關系很多人以為歸并排序只是教科書內容現實中都用內置排序。其實很多現代編程語言內置排序正是歸并排序的改良版本。比如某些語言標準庫里的排序算法是 TimSort它的核心思想是找到數組中已經有序的“run”然后用歸并的方式把這些 run 合并起來同時在小規(guī)模時切換到插入排序?？梢哉f TimSort 就是“歸并排序 插入排序 自然有序檢測”的混合體。理解歸并排序的價值不只是為了面試。當你遇到一個近似有序的大數組時原生快排可能表現平庸而基于歸并思想的 TimSort 卻能在 O(n) 時間完成排序。當你需要統(tǒng)計逆序對時歸并排序是標準答案。當你處理鏈表時歸并排序又是空間效率最高的穩(wěn)定排序。這也是為什么它作為“經典排序”的地位一直沒有被替代。6. 怎么選歸并排序 vs 快排 vs 堆排的實戰(zhàn)對比6.1 不同數據形態(tài)下的表現差異我用一組相對可控的實驗數據說明一下感受。以下耗時不是精確基準值但比例能反映算法差異環(huán)境是一臺普通開發(fā)機語言是 Python數據規(guī)模從十萬到一千萬。數據形態(tài)歸并排序快速排序堆排序10 萬隨機整數約 0.04 秒約 0.03 秒約 0.06 秒100 萬隨機整數約 0.5 秒約 0.35 秒約 1.1 秒100 萬近似有序約 0.08 秒帶跳過優(yōu)化約 0.05 秒pivot 選擇好時約 1.0 秒100 萬大量重復值約 0.4 秒約 0.3 秒約 1.2 秒1000 萬隨機整數約 7 秒內存占用顯著約 5 秒約 15 秒從這張表可以看出幾個規(guī)律歸并排序在任何數據形態(tài)下都比較穩(wěn)定但常數因子不是最小的快排在重復值和隨機數上通常最快但遇到特定退化的 pivot 選擇可能變慢且不穩(wěn)定堆排序常數最大它的優(yōu)勢主要在內存占用固定、無遞歸以及優(yōu)先級隊列場景而不是單純排序。6.2 工程選型的判斷清單如果你的需求里包含下面任意一條優(yōu)先考慮歸并排序第一要求排序穩(wěn)定相同元素順序不能變第二數據源是鏈表結構第三數據量超過內存需要外部排序第四需要順便統(tǒng)計逆序對第五實時系統(tǒng)希望排序耗時盡量可預測不管輸入是否有序。如果你內存非常緊張比如單片機環(huán)境歸并排序 O(n) 的輔助空間可能不可接受。此時要么選堆排序用 O(1) 空間換一個不那么快的排序時間要么選快排的原地分區(qū)版本。如果數據結構是數組、內存充足而且只關注速度快排往往更好。如果排序目標是基礎類型且不需要穩(wěn)定很多語言的原生雙軸快排已經優(yōu)化得很好也不一定要自己寫歸并。6.3 一點個人體會我從第一次寫歸并排序到現在最大的感受是它的思想價值大于代碼價值。遞歸拆分讓我們學會用對數視角看待問題合并過程讓我們理解穩(wěn)定性從何而來復雜度推導讓我們知道層數和每層代價這兩個維度構成了算法分析的基本框架。這些能力可以直接遷移到很多非排序問題上。如果你正在準備面試不要只背代碼試著在白板上推導一遍 T(n) 2T(n/2) O(n)再手動模擬一個長度為 7 的數組的業(yè)務流程然后把遞歸版改成迭代版最后自己加上逆序對計數。這一套走完歸并排序才算真正吃透了。工作中如果你碰到一個要求穩(wěn)定排序的大數據場景或者需要把多個有序文件合并成一個你會感謝現在花時間把這些細節(jié)弄明白的自己。 歸并排序原理與復雜度詳解：從分治思想到工程落地
1. 歸并排序到底在做什么分治思想與執(zhí)行流程歸并排序是被討論最多但也是最容易被輕視的經典排序之一。它的平均時間復雜度穩(wěn)定在 O(nlog2n)無論輸入是剛好亂序還是接近有序這個上界都不會變。很多人能背出遞歸代碼卻說不清為什么需要臨時數組、為什么先遞歸再合并、為什么合并過程一定要雙指針。這篇文章想把歸并排序從思想層到代碼層徹底拆開先講它到底在做什么再推導 O(nlog2n) 的來源然后給出可直接復用的遞歸版和迭代版實現最后聊工程落地時真正值得注意的坑和優(yōu)化。適合讀這篇內容的人有兩類一類是準備技術面試的開發(fā)者歸并排序幾乎是必考點而且經常衍生出逆序對、鏈表排序、外部排序等問題另一類是工作中要寫數據處理工具的工程師需要在大數據量排序時選對算法。文章里的代碼我以 Python 為主但思路可以平移到任何語言。1.1 分治思想拆解不是“把一個數組拆開”這么簡單分治策略有三個動作分解、解決、合并。歸并排序對這三個動作的執(zhí)行順序非常明確先遞歸地把數組分成兩半直到每個子數組只剩一個元素然后開始逐步合并合并過程中完成排序。這里很多人有一個誤區(qū)以為歸并排序的核心是“拆分”。其實拆分只是輔助手段真正的排序發(fā)生在合并階段。把一個數組拆到只剩一個元素時每個子數組天然有序因為單個元素不需要比較。接下來要做的就是把兩個已經各自有序的數組按照大小關系合并成一個新的有序數組。這種“把無序數組變成若干有序片段再通過有序片段合并得到整體有序”的思路才是歸并排序區(qū)別于冒泡、選擇這些暴力排序的本質。另一個容易混淆的點歸并排序和快速排序都用了分治但方向是相反的?？炫攀窃诜謪^(qū)之后就對數據做了調整使得基準值左邊的數據都小于等于它、右邊的數據都大于等于它然后遞歸處理左右兩邊而歸并排序先遞歸到底排序實際發(fā)生在“歸”回來的路上。這也是為什么歸并排序在合并時需要輔助空間而快排可以在原數組上通過交換完成分區(qū)。1.2 合并兩個有序數組整個算法的靈魂假設你有兩個已經排好序的數組比如 [1, 3, 5] 和 [2, 4, 6]要把它們合并成一個有序數組最自然的做法是雙指針一個指針指向左數組開頭一個指針指向右數組開頭每次比較兩個指針指向的元素較小的放入結果數組然后對應指針后移。如果某一方先走完就把另一方的剩余元素直接接到結果后面。這個過程看起來簡單但它決定了歸并排序的穩(wěn)定性。如果我們比較的時候使用arr[i] arr[j]而不是那么兩個相等的元素會優(yōu)先取左邊的這樣在合并過程中不會破壞相同元素的原始相對順序。穩(wěn)定性在業(yè)務場景里非常關鍵比如先按時間排序、再按優(yōu)先級排序如果第二次排序是不穩(wěn)定的第一次排序的順序就白做了。合并兩個有序數組的操作就是 merge。整個歸并排序的執(zhí)行過程可以理解成無數個 merge 嵌套在一起最小規(guī)模是兩個長度為 1 的數組合并成長度為 2 的有序數組然后兩個長度為 2 的數組合并成長度為 4 的有序數組一層一層向上直到最后兩個長度為 n/2 的數組被合并成完整的 n 長度數組。1.3 手動模擬一趟完整合并建立遞歸直覺用經典的數組 [38, 27, 43, 3, 9, 82, 10] 走一遍。先按中點拆分成 [38, 27, 43, 3] 和 [9, 82, 10]左半部分繼續(xù)拆成 [38, 27] 和 [43, 3]再拆成 [38]、[27]、[43]、[3]。從最底層開始合并[38] 和 [27] 合并成 [27, 38][43] 和 [3] 合并成 [3, 43]然后這兩個有序數組再合并成 [3, 27, 38, 43]。另一邊也做同樣的事情[9, 82, 10] 拆成 [9]、[82]、[10]合并后得到 [9, 10, 82]。最后兩個有序數組 [3, 27, 38, 43] 和 [9, 10, 82] 雙指針合并得到 [3, 9, 10, 27, 38, 43, 82]排序完成。注意整個過程的執(zhí)行順序是深度優(yōu)先的先一路拆到最左邊的最底層完成合并再回來處理右邊的分支。這也是遞歸程序的特點理解這一點后寫代碼時就不會糾結為什么合并函數要在兩次遞歸調用之后才執(zhí)行。2. O(nlog2n) 是怎么算出來的復雜度推導與直覺2.1 從遞推公式到遞歸樹假設輸入規(guī)模為 n歸并排序把問題拆成兩個大小為 n/2 的子問題每個子問題的代價是 T(n/2)合并兩個有序子數組需要掃描所有 n 個元素代價是 O(n)。于是可以得到遞推式T(n) 2T(n/2) O(n)邊界條件是 T(1) O(1)因為單個元素不需要任何比較。把遞推式一層層展開T(n) 2T(n/2) n 2(2T(n/4) n/2) n 4T(n/4) 2n 8T(n/8) 3n ... (2^k)T(n/2^k) k*n當遞歸到達底層時n/2^k 1也就是 k log2n。代入后得到 T(n) n*T(1) log2n * n O(nlog2n)。這個推導過程建議親手寫一遍。很多面試里問“歸并排序為什么是 O(nlog2n)”本質上考的不是你能不能背出結論而是能不能從遞推式出發(fā)解釋層數和每層代價。遞歸樹法和這個展開是等價的樹的高度是 log2n每一層所有子問題加起來都要處理 n 個數據所以總代價是 n 乘以樹高。2.2 層數為什么是 log2n一個生活化類比可以把歸并排序想象成一個班級廣播通知的下發(fā)過程一個老師告訴兩位班長兩位班長各自告訴四位組長四位組長再告訴八位組員。每次信息傳遞量翻倍從 1 到 n需要的層數就是從 n 除以 2 一直到 1 的除法次數也就是 log2n。歸并排序的遞歸樹高度正好是這樣的對數結構。每層合并代價都是 O(n) 這一點也值得展開。第 0 層只有一次合并掃描 n 個元素第 1 層有兩次合并每次掃描 n/2 個元素加總還是 n第 2 層有四次合并每次掃描 n/4 個元素加總依然是 n。無論哪一層所有合并操作的總掃描長度都是 n。這個規(guī)律貫穿整個算法所以復雜度就是“層數乘以每層代價”即 log2n 乘以 n。說到這里必須提醒一點O(nlog2n) 是平均時間復雜度同時也是最好和最壞時間復雜度。歸并排序不會因為輸入已經有序而減少比較次數也不會因為輸入完全逆序而增加比較次數。這一點和插入排序形成鮮明對比插入排序的最好情況只有 O(n)。歸并排序的這種確定性在實時性要求高的場景里是優(yōu)勢在追求極致性能的緩存場景里也可能成為劣勢這點后續(xù)會展開。2.3 空間復雜度與穩(wěn)定性為什么臨時數組是剛需歸并排序的空間復雜度是 O(n)因為每次合并兩個有序數組時需要一個和整體規(guī)模等長的臨時數組來存放結果。遞歸調用本身的棧深度是 log2n所以如果嚴格計算總空間占用是 O(n) 加上 O(log2n) 的函數棧但 O(log2n) 被 O(n) 主導通常就記作 O(n)。很多人會問能不能不用臨時數組在原數組上直接完成歸并如果嚴格要求原地也可以做但要么用復雜的原地旋轉算法把時間復雜度推到 O(nlog2n) 上方要么犧牲排序穩(wěn)定性工程上都不劃算。一個更常見的做法是預先分配一個長度為 n 的臨時數組在遞歸過程中反復使用它而不是每次 merge 都新建數組。這樣空間開銷只是 O(n)不會變成 O(nlog2n)。穩(wěn)定性來源于合并時對相等元素的處理。如果寫成if arr[i] arr[j]相等的時候先取左半部分那么原始順序就被保留了。如果寫成相等時先取右半部分穩(wěn)定性就被破壞。很多初寫歸并排序的人在這里不小心寫錯導致排序結果正確但“穩(wěn)定排序”的名頭丟了。3. 遞歸版與迭代版完整實現代碼是最快的說明書3.1 遞歸實現的正確姿勢遞歸版歸并排序的代碼結構非常固定外層是排序函數內層是合并函數。一個容易踩的坑是臨時數組的處理。不要在遞歸函數內部反復創(chuàng)建數組正確的做法是在入口函數里一次性創(chuàng)建好然后作為參數向下傳遞。def merge(arr, left, mid, right, temp): i, j, k left, mid 1, left while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 for t in range(left, right 1): arr[t] temp[t] def merge_sort_recursive(arr, left, right, temp): if left right: return mid left (right - left) // 2 merge_sort_recursive(arr, left, mid, temp) merge_sort_recursive(arr, mid 1, right, temp) merge(arr, left, mid, right, temp) def merge_sort(arr): temp [0] * len(arr) merge_sort_recursive(arr, 0, len(arr) - 1, temp)注意兩點mid left (right - left) // 2而不是(left right) // 2后者在極端情況下可能產生整數溢出雖然 Python 的整數不會溢出但其他語言需要養(yǎng)成這個習慣。另外合并結束后要把臨時數組拷貝回原數組。這里用的是循環(huán)拷貝如果是在 Python 里也可以直接用切片arr[left:right1] temp[left:right1]但循環(huán)更便于理解也避免了切片帶來的額外對象開銷。3.2 自底向上的迭代實現遞歸實現的缺點是當數組規(guī)模特別大時遞歸深度會達到 log2n雖然不容易爆棧但在某些嵌入式環(huán)境或函數棧極小的環(huán)境里仍然不放心。迭代版自底向上實現完全避開遞歸方法是從合并長度為 1 的子數組開始循環(huán)處理長度為 2、4、8 直到整個數組。def merge_sort_iter(arr): n len(arr) if n 2: return arr temp [0] * n width 1 while width n: left 0 while left n: mid min(left width - 1, n - 1) right min(left 2 * width - 1, n - 1) if mid right: merge(arr, left, mid, right, temp) left 2 * width width * 2 return arr這里的 merge 函數和遞歸版共用。迭代版的核心是width每次翻倍left 每次前進2 * width保證當前合并的兩個區(qū)間分別是 [left, mid] 和 [mid1, right]。當數組長度不是 2 的冪時需要借助min對 mid 和 right 做鉗制。if mid right這個判斷很重要如果不加當左區(qū)間已經包含數組剩余全部元素時合并會去訪問一個不存在的右區(qū)間。3.3 兩種寫法在工程上如何取舍遞歸版更符合分治思想代碼可讀性好調試的時候可以用調用棧直觀看到分解過程。迭代版代碼稍顯繁瑣但避免了遞歸調用開銷在數據規(guī)模極大時更穩(wěn)。我個人的習慣是日常業(yè)務代碼用遞歸版因為邏輯清楚、不易出錯底層工具或需要極致穩(wěn)定性的場景用迭代版。下表簡單對比兩種實現的差異維度遞歸版迭代版代碼可讀性高和思想一一對應低需要理解 width 和 left 的推進關系函數調用開銷有但影響通?？珊雎詿o遞歸純循環(huán)?？臻g壓力需要 O(log2n) 遞歸棧幾乎不需要額外棧邊界處理難度較簡單需要小心鉗制 mid 和 right適用場景面試、業(yè)務排序、教學嵌入式環(huán)境、超大數組、無遞歸環(huán)境4. 工程落地避坑指南邊界、內存與微優(yōu)化4.1 最容易被忽略的邊界條件歸并排序寫錯的原因通常不是算法思想不對而是邊界處理不到位。第一個高頻錯誤是遞歸終止條件寫成left right這本身也能工作但會多一層無意義的遞歸更規(guī)范的是left right。第二個高頻錯誤是對mid的劃分。假設數組下標是 [left, right]左區(qū)間應該是 [left, mid]右區(qū)間是 [mid1, right]。如果錯誤地把右區(qū)間寫成 [mid, right]左區(qū)間會多一個元素最終排序結果雖然可能正確但會讓兩個區(qū)間不均衡破壞了歸并排序的分治邏輯甚至可能導致死循環(huán)。而且 mid 的計算方式必須和迭代版的鉗制邏輯一致否則左右區(qū)間會出現重疊或漏掉元素。第三個錯誤出現在合并后的拷貝階段。有些人只把臨時數組的一部分拷回原數組比如從 0 開始拷到 right-left卻沒有考慮 left 的偏移量。當 left 不是 0 時這種寫法會污染原數組里不屬于當前合并范圍的元素。正確的做法是從 left 開始循環(huán)到 right把 temp 對應位置拷回去。4.2 臨時數組分配策略統(tǒng)一分配還是每次創(chuàng)建很多初學版本的代碼長這樣在 merge 函數內部temp [0] * (right - left 1)看起來沒錯但每次遞歸調用都要重新分配數組整體空間分配次數等于合并次數約為 n 次量級。對于十萬元素或許還能忍受對于百萬千萬級數據創(chuàng)建大量臨時對象不僅耗時還容易觸發(fā)內存碎片。工程上的標準做法是在入口函數里一次性分配temp [0] * n之后所有遞歸層級共用這一塊空間。這是因為每次合并只需要訪問當前區(qū)間對應的位置不同分支遞歸并不會同時使用 temp 數組所以不存在數據覆蓋問題。這種方法把動態(tài)內存分配從 O(n) 次降低到常數次效果非常明顯。4.3 三個值得做的微優(yōu)化第一個優(yōu)化是小區(qū)間切換插入排序。當待排序區(qū)間長度小于某個閾值常用 16 或 32時不再繼續(xù)拆分和合并而是直接對小區(qū)間做插入排序。插入排序在規(guī)模小的時候常數因子遠小于歸并排序而且緩存友好。這個優(yōu)化是很多工業(yè)級排序庫的基礎做法。def merge_sort_optimized(arr, left, right, temp): if right - left 16: insertion_sort(arr, left, right) return mid left (right - left) // 2 merge_sort_optimized(arr, left, mid, temp) merge_sort_optimized(arr, mid 1, right, temp) if arr[mid] arr[mid 1]: return merge(arr, left, mid, right, temp)第二個優(yōu)化是判斷是否真的需要合并。如果左區(qū)間最后一個元素已經小于等于右區(qū)間第一個元素說明兩個區(qū)間已經天然有序整段不需要做任何操作。這個判斷只需要 O(1) 時間卻能在處理近似有序數組時跳過大量合并直接把最好情況的時間復雜度從 O(nlog2n) 降到 O(n)。它和插入排序的近似有序友好特性殊途同歸。第三個優(yōu)化是減少元素的重復拷貝。標準寫法每次合并完都把 temp 拷回 arr下一層合并又把 arr 拷到 temp。如果交替使用 arr 和 temp 作為目標數組可以讓數據在兩層之間直接往返省掉一部分拷貝。實現起來要復雜一些性能提升通常在 10% 到 20% 之間適合對性能有極致要求的讀者自己去研究業(yè)務場景不一定需要。4.4 常見錯誤與排查思路如果排序結果只是部分有序先檢查合并后拷貝的區(qū)間是否完整。如果數組完全沒排序檢查遞歸調用時 mid 的左右區(qū)間是否寫反。如果出現越界異常檢查 while 循環(huán)的終止條件是否寫成i mid而不是i mid。這些錯誤在調試時不一定要看完整數組可以用小規(guī)模隨機數組反復跑再對比 Python 內置的sorted()結果很快能定位。另一個實用技巧是在合并函數入口加一個斷言assert left mid right確保調用 merge 時區(qū)間參數合法。很多問題不是算法問題而是調用方沒有正確傳入區(qū)間范圍。加斷言后測試階段就能暴露問題而不是等線上數據出錯。5. 歸并排序的經典變體與應用場景5.1 逆序對統(tǒng)計merge 時的天然能力逆序對定義是如果 i j 且 arr[i] arr[j]這一對元素就是一個逆序對。暴力解法雙重循環(huán)需要 O(n2) 時間而歸并排序可以在合并過程中順手統(tǒng)計時間復雜度降到 O(nlog2n)。原理其實很巧妙。合并兩個有序子數組時當右區(qū)間的當前元素arr[j]小于左區(qū)間的當前元素arr[i]說明從 i 到 mid 的所有元素都大于arr[j]它們每一個都和arr[j]構成逆序對。此時一次性累加mid - i 1個逆序對而不是一個個比較。def merge_count(arr, left, mid, right, temp): i, j, k left, mid 1, left inv 0 while i mid and j right: if arr[i] arr[j]: temp[k] arr[i] i 1 else: temp[k] arr[j] j 1 inv mid - i 1 k 1 while i mid: temp[k] arr[i] i 1 k 1 while j right: temp[k] arr[j] j 1 k 1 for t in range(left, right 1): arr[t] temp[t] return inv這個寫法注意一點只有arr[i] arr[j]時才計數等于的情況不計。因為等于不是逆序對用取左區(qū)間元素可以保證穩(wěn)定性也不會多算逆序對。面試中經常把它作為歸并排序的進階題理解了這一行計數邏輯就掌握了一套高頻解題思路。5.2 外部排序與多路歸并如果數據量遠超內存比如幾十 GB 的日志文件要在內存只有幾個 GB 的機器上排序普通快排或者歸并都不能一次性完成。這時會用到外部排序而外部排序的核心就是把歸并排序的思路放大到文件級別。基本流程是把大文件切分成多個可讀入內存的塊每塊讀入內存后用快排或歸并排好序寫回磁盤形成多個臨時有序文件最后對這些有序文件做多路歸并。多路歸并不能簡單兩個文件兩兩合并因為那樣會產生大量磁盤 IO工程上一般用優(yōu)先隊列維護 k 個文件的最小元素每次取最小寫回輸出文件同時從對應文件補一個元素進來。這個過程本質上是 k 路歸并。之所以還是叫“歸并”是因為它和內存歸并排序共享同一個核心操作合并多個有序序列。區(qū)別只在于數據載體是文件以及為了減少磁盤 IO 引入的緩沖區(qū)設計?？梢哉f如果不理解歸并排序外部排序就很難展開這也是為什么很多大數據工程師會回頭補排序算法的底層知識。5.3 鏈表排序歸并排序的真正主場數組排序時歸并排序需要 O(n) 額外空間這是它對比快排的最大劣勢。但如果是鏈表排序歸并排序不需要額外開辟存儲空間因為鏈表節(jié)點之間的指針可以在合并時重新連接不需要新的節(jié)點數組。額外開銷只有遞歸函數棧 O(log2n)這比數組歸并要好得多。鏈表歸并的核心思路用快慢指針找到鏈表中點切成左右兩條鏈表遞歸排序后再用雙指針合并兩條有序鏈表。找中點的代碼我經?？吹接腥藢戝edef merge_sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next right_head merge_sort_list(slow.next) slow.next None left_head merge_sort_list(head) return merge_two_lists(left_head, right_head)這里 fast 從head.next開始走可以讓 slow 恰好停在左半部分的最后一個節(jié)點。如果 fast 也從 head 開始slow 可能會停在偏右的位置拆分就不準了。合并兩條有序鏈表的函數則是典型的雙哨兵節(jié)點技巧這里不再展開。5.4 與主流排序庫的關系很多人以為歸并排序只是教科書內容現實中都用內置排序。其實很多現代編程語言內置排序正是歸并排序的改良版本。比如某些語言標準庫里的排序算法是 TimSort它的核心思想是找到數組中已經有序的“run”然后用歸并的方式把這些 run 合并起來同時在小規(guī)模時切換到插入排序?？梢哉f TimSort 就是“歸并排序 插入排序 自然有序檢測”的混合體。理解歸并排序的價值不只是為了面試。當你遇到一個近似有序的大數組時原生快排可能表現平庸而基于歸并思想的 TimSort 卻能在 O(n) 時間完成排序。當你需要統(tǒng)計逆序對時歸并排序是標準答案。當你處理鏈表時歸并排序又是空間效率最高的穩(wěn)定排序。這也是為什么它作為“經典排序”的地位一直沒有被替代。6. 怎么選歸并排序 vs 快排 vs 堆排的實戰(zhàn)對比6.1 不同數據形態(tài)下的表現差異我用一組相對可控的實驗數據說明一下感受。以下耗時不是精確基準值但比例能反映算法差異環(huán)境是一臺普通開發(fā)機語言是 Python數據規(guī)模從十萬到一千萬。數據形態(tài)歸并排序快速排序堆排序10 萬隨機整數約 0.04 秒約 0.03 秒約 0.06 秒100 萬隨機整數約 0.5 秒約 0.35 秒約 1.1 秒100 萬近似有序約 0.08 秒帶跳過優(yōu)化約 0.05 秒pivot 選擇好時約 1.0 秒100 萬大量重復值約 0.4 秒約 0.3 秒約 1.2 秒1000 萬隨機整數約 7 秒內存占用顯著約 5 秒約 15 秒從這張表可以看出幾個規(guī)律歸并排序在任何數據形態(tài)下都比較穩(wěn)定但常數因子不是最小的快排在重復值和隨機數上通常最快但遇到特定退化的 pivot 選擇可能變慢且不穩(wěn)定堆排序常數最大它的優(yōu)勢主要在內存占用固定、無遞歸以及優(yōu)先級隊列場景而不是單純排序。6.2 工程選型的判斷清單如果你的需求里包含下面任意一條優(yōu)先考慮歸并排序第一要求排序穩(wěn)定相同元素順序不能變第二數據源是鏈表結構第三數據量超過內存需要外部排序第四需要順便統(tǒng)計逆序對第五實時系統(tǒng)希望排序耗時盡量可預測不管輸入是否有序。如果你內存非常緊張比如單片機環(huán)境歸并排序 O(n) 的輔助空間可能不可接受。此時要么選堆排序用 O(1) 空間換一個不那么快的排序時間要么選快排的原地分區(qū)版本。如果數據結構是數組、內存充足而且只關注速度快排往往更好。如果排序目標是基礎類型且不需要穩(wěn)定很多語言的原生雙軸快排已經優(yōu)化得很好也不一定要自己寫歸并。6.3 一點個人體會我從第一次寫歸并排序到現在最大的感受是它的思想價值大于代碼價值。遞歸拆分讓我們學會用對數視角看待問題合并過程讓我們理解穩(wěn)定性從何而來復雜度推導讓我們知道層數和每層代價這兩個維度構成了算法分析的基本框架。這些能力可以直接遷移到很多非排序問題上。如果你正在準備面試不要只背代碼試著在白板上推導一遍 T(n) 2T(n/2) O(n)再手動模擬一個長度為 7 的數組的業(yè)務流程然后把遞歸版改成迭代版最后自己加上逆序對計數。這一套走完歸并排序才算真正吃透了。工作中如果你碰到一個要求穩(wěn)定排序的大數據場景或者需要把多個有序文件合并成一個你會感謝現在花時間把這些細節(jié)弄明白的自己。