考題：合併 K 個排序串列 Problem: merge k sorted lists · 演算法 Algorithms

考題：合併 K 個排序串列

一個一個合併是 O(kN)；用堆積每次挑最小的開頭，或兩兩分治合併，都降到 O(N log k)。

解法

串列數 k4

每串長度4

題目

把 k 個排好序的串列合併成一個排好序的串列。例如 [1,4,5]、[1,3,4]、[2,6] → [1,1,2,3,4,4,5,6]。N 是全部值的個數。

1/18

結果

堆積（由小到大）：第 #1 #0 #2 #3 個串列

下一個還沒讀的值堆積頂端剛取出

把 4 個串列的第一個值放進最小堆積。

同一份輸入，所有解法
解法	答案	比較次數	額外記憶體	Big O
一個一個合併	16 個，已排序	31	複製 16 個	O(kN)
堆積挑最小的開頭	16 個，已排序	38	堆積 4 個	O(N log k)
兩兩分治合併	16 個，已排序	28	複製 16 個	O(N log k)

亮起來的是這一步執行的程式碼

1function mergeTwo(a: number[], b: number[]): number[] {
2  const out: number[] = [];
3  let i = 0, j = 0;
4  while (i < a.length && j < b.length) {
5    if (b[j] < a[i]) out.push(b[j++]);
6    else out.push(a[i++]);
7  }
8  return out.concat(a.slice(i), b.slice(j));
9}
10 
11// O(kN): the merged list is re-read every time another one is added.
12function mergeOneByOne(lists: number[][]): number[] {
13  let acc: number[] = [];
14  for (const list of lists) acc = mergeTwo(acc, list);
15  return acc;
16}
17 
18// O(N log k): a min-heap holds each list's next value.
19function mergeHeap(lists: number[][]): number[] {
20  const heap: [number, number, number][] = [];           // [value, list, index]
21  const less = (x: number[], y: number[]) => x[0] < y[0] || (x[0] === y[0] && x[1] < y[1]);
22  const push = (e: [number, number, number]) => {
23    heap.push(e);
24    for (let i = heap.length - 1; i > 0 && less(heap[i], heap[(i - 1) >> 1]); i = (i - 1) >> 1) {
25      [heap[i], heap[(i - 1) >> 1]] = [heap[(i - 1) >> 1], heap[i]];
26    }
27  };
28  const pop = (): [number, number, number] => {
29    const top = heap[0], last = heap.pop()!;
30    if (heap.length) {
31      heap[0] = last;
32      for (let i = 0; ; ) {
33        const l = 2 * i + 1, r = l + 1;
34        let m = i;
35        if (l < heap.length && less(heap[l], heap[m])) m = l;
36        if (r < heap.length && less(heap[r], heap[m])) m = r;
37        if (m === i) break;
38        [heap[i], heap[m]] = [heap[m], heap[i]];
39        i = m;
40      }
41    }
42    return top;
43  };
44  lists.forEach((list, k) => { if (list.length) push([list[0], k, 0]); });
45  const out: number[] = [];
46  while (heap.length) {
47    const [value, k, i] = pop();
48    out.push(value);
49    if (i + 1 < lists[k].length) push([lists[k][i + 1], k, i + 1]);
50  }
51  return out;
52}
53 
54// O(N log k): merge in pairs, halving the number of lists each round.
55function mergeDivide(lists: number[][]): number[] {
56  let current = lists;
57  while (current.length > 1) {
58    const next: number[][] = [];
59    for (let i = 0; i < current.length; i += 2) {
60      next.push(i + 1 < current.length ? mergeTwo(current[i], current[i + 1]) : current[i]);
61    }
62    current = next;
63  }
64  return current[0] ?? [];
65}

模型假設與範圍

Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

面試先說「兩兩合併的函式」怎麼寫（合併兩個排序串列是基本功），再指出一個一個合併會一直重讀前面的結果，改用堆積挑最小的開頭。
不想寫堆積時，兩兩分治合併一樣是 O(N log k)，而且只用到合併兩個串列的函式。

和其他主題的關係

由這些組成: 資料結構 · 堆積資料結構 · 鏈結串列分治與遞迴樹

時間與空間複雜度（Big O）

操作	平均	最差
一個一個合併第 i 次合併要重讀前面 i 個串列	O(kN)	O(kN)
堆積挑最小的開頭堆積裡永遠只有 k 個	O(N log k)	O(N log k)
兩兩分治合併 log k 輪，每輪每個值讀一次	O(N log k)	O(N log k)

空間：O(1) / O(k) / O(1)，串列重新串接、不複製時；陣列版本另外要 O(N)

Big O 實測：n 變大時步數怎麼長

數的是：比較次數（n 是串列數 k，每串 50 個值）

	Big O	n = 4	n = 16	n = 64	成長倍數：實測（理論）
一個一個合併	O(n²)	445	6,642	101,206	×227 (×256)
堆積挑最小的開頭	O(n log n)	482	4,409	29,448	×61 (×48)
兩兩分治合併	O(n log n)	396	3,159	19,059	×48 (×48)

每串長度固定時，N 和 k 成正比，所以 O(kN) 看起來是 k²，O(N log k) 是 k log k。

和其他做法比

	k = 4（N = 200）	k = 16（N = 800）	k = 64（N = 3,200）
一個一個合併	445	6,642	101,206
堆積挑最小的開頭	482	4,409	29,448
兩兩分治合併	396	3,159	19,059

每個串列 50 個值，數比較次數。k 從 4 變成 64（16 倍），一個一個合併變成 227 倍——前面合好的部分每加一個串列就重讀一次；堆積和兩兩合併都只變成大約 48 倍。

真實世界裡的它

LeetCode 23（合併 K 個排序串列）；外部排序：資料大到記憶體放不下時，先切成排序好的小檔，再做 k 路合併。
資料庫的 LSM tree（Log-Structured Merge tree）合併（compaction）、搜尋引擎合併多個分片的結果，都是同一招。

取捨與陷阱

Python 的 heapq 遇到相同的值會去比下一個欄位：放 (值, 串列編號, 索引) 而不是節點物件，否則會比較節點而出錯。
空串列要先跳過，不然一開始就會對空串列取第一個值。
O(kN) 和 O(N log k) 在 k 很小時差不多；差距是 k 變大時才出現（見下表）。

演算法