Merge sort — Divide & conquer, stable, foundation cho external sort

TL;DR: Merge sort là bài mẫu của paradigm divide & conquer — chia đôi, sort từng nửa đệ quy, merge 2 nửa đã sorted. Recurrence T(n) = 2T(n/2) + n giải ra O(n log n) với recursion tree: mỗi trong log₂ n level đóng góp đúng n work. Best = average = worst = O(n log n) — không adaptive (Quick sort cũng không adaptive; adaptive là TimSort, không phải Quick sort). Stable vì merge step ưu tiên left half khi tie. Trade-off chính: cần O(n) buffer phụ (không in-place). Nền tảng của external merge sort (sort 100GB trên 16GB RAM), TimSort (Java/Python default), và k-way merge trong Lucene.

Cần sort 100GB log file trên máy chỉ có 16GB RAM. Quick sort không vào nổi RAM một lần — không có cách nào load toàn bộ 100GB vào memory để partition. Merge sort giải quyết vấn đề này bằng cách chia file thành các chunk vừa RAM (ví dụ 8GB mỗi chunk), sort từng chunk trong memory, rồi merge tất cả chunk đã sorted lại với nhau — đó là external sort production-grade mà PostgreSQL, MySQL, và Hadoop dùng khi data vượt work_mem.

Cùng cấu trúc đệ quy còn xuất hiện trong parallel sort (Arrays.parallelSort), k-way merge (Lucene segment merge), và TimSort (merge step của sort Object array mặc định).

Bài này dạy merge sort từ recurrence T(n) = 2T(n/2) + O(n) — chứng minh O(n log n) bằng recursion tree, pseudocode đầy đủ với buffer optimization, và nền tảng cho external merge sort (bài 08).

1. Analogy — Sắp 100 quân bài chia 4 người

Hình dung bạn có 100 quân bài xáo trộn và 4 người bạn sẵn sàng giúp.

Bước 1: chia đều 25 quân cho mỗi người. Cả 4 người sắp xếp phần của mình song song — không ai phụ thuộc ai.

Bước 2: khi cả 4 xong, mỗi người đặt 25 quân đã sorted của mình thành một cọc riêng. Bạn nhìn vào đỉnh của 4 cọc, chọn quân nhỏ nhất, lấy ra và đặt vào pile kết quả. Người vừa mất quân đó lật quân tiếp theo lên. Lặp lại cho đến khi 4 cọc hết.

Kết quả: 100 quân sorted mà không ai phải cầm toàn bộ 100 quân cùng lúc.

2. Divide & conquer recipe

Merge sort là bài mẫu của paradigm divide & conquer. Recipe gồm 3 bước:

Divide: chia input thành sub-problem nhỏ hơn, không overlap. Merge sort: chia array đôi tại midpoint.

Conquer: giải từng sub-problem bằng đệ quy. Base case khi sub-problem đủ nhỏ (array 1 phần tử đã là sorted).

Combine: ghép kết quả từ sub-problem thành kết quả cho problem gốc. Merge sort: merge 2 sorted half thành 1 sorted array.

Recurrence tổng quát cho divide & conquer:

T(n) = a × T(n/b) + f(n)
-- a = số sub-problem
-- b = factor chia nhỏ
-- f(n) = work ở bước combine

Merge sort cụ thể: a = 2 (chia làm 2 nửa), b = 2 (mỗi nửa bằng n/2), f(n) = O(n) (merge step quét qua toàn bộ phần tử). Suy ra:

T(n) = 2T(n/2) + O(n)

3. Complexity — recursion tree proof

Để giải T(n) = 2T(n/2) + n, vẽ recursion tree và đếm work ở mỗi level:

Level 0:  [  n  ]                        work = n
           /    \
Level 1: [n/2] [n/2]                     work = n/2 + n/2 = n
         / \   / \
Level 2:[n/4][n/4][n/4][n/4]             work = 4 × n/4 = n
         ...
Level k: 2^k nodes, mỗi node work n/2^k  work = 2^k × n/2^k = n
         ...
Level log₂n: n nodes, mỗi node work 1    work = n

Mỗi level đóng góp đúng n work. Số level = log₂ n (vì chia đôi liên tục đến khi còn 1 phần tử). Tổng:

T(n) = n × log₂n = O(n log n)

Best = average = worst = O(n log n). Merge sort không adaptive — dù input đã sorted hay sorted ngược, thuật toán vẫn chia đôi và merge đủ log n level. So sánh với Quick sort: same O(n log n) average nhưng O(n²) worst case khi pivot chọn xấu.

Space: O(n) buffer cho merge step, cộng thêm O(log n) recursion stack. Merge sort không in-place — đây là trade-off so với Quick sort.

graph TD
    N["[5,2,4,6,1,3]<br/>n work"]
    L["[5,2,4]<br/>n/2 work"]
    R["[6,1,3]<br/>n/2 work"]
    LL["[5,2]"]
    LM["[4]"]
    RL["[6,1]"]
    RM["[3]"]
    LLL["[5]"]
    LLR["[2]"]
    RLL["[6]"]
    RLR["[1]"]
    ML1["merge → [2,5]"]
    ML2["merge → [2,4,5]"]
    MR1["merge → [1,6]"]
    MR2["merge → [1,3,6]"]
    MFIN["merge → [1,2,3,4,5,6]"]

    N --> L
    N --> R
    L --> LL
    L --> LM
    R --> RL
    R --> RM
    LL --> LLL
    LL --> LLR
    RL --> RLL
    RL --> RLR
    LLL --> ML1
    LLR --> ML1
    ML1 --> ML2
    LM --> ML2
    RLL --> MR1
    RLR --> MR1
    MR1 --> MR2
    RM --> MR2
    ML2 --> MFIN
    MR2 --> MFIN

4. Pseudocode đầy đủ

4.1 Top-down đệ quy

MergeSort(A):
    if A.length < 2: return
    buf <- mảng phụ kích thước A.length  -- cấp phát 1 lần, dùng lại
    Sort(A, buf, 0, A.length - 1)

Sort(A, buf, lo, hi):
    if lo >= hi: return
    mid <- lo + (hi - lo) / 2            -- tránh overflow: KHÔNG dùng (lo + hi) / 2
    Sort(A, buf, lo, mid)
    Sort(A, buf, mid + 1, hi)
    Merge(A, buf, lo, mid, hi)

Merge(A, buf, lo, mid, hi):
    -- sao chép đoạn [lo..hi] sang buf để đọc từ buf trong khi ghi vào A
    for k <- lo đến hi: buf[k] <- A[k]

    i <- lo; j <- mid + 1; k <- lo
    while i <= mid và j <= hi:
        if buf[i] <= buf[j]:             -- <= giữ STABLE sort
            A[k] <- buf[i]; i <- i + 1
        else:
            A[k] <- buf[j]; j <- j + 1
        k <- k + 1
    while i <= mid:                      -- sao chép phần còn lại của nửa trái
        A[k] <- buf[i]; i <- i + 1; k <- k + 1
    -- nửa phải đã ở đúng vị trí trong A, không cần copy

Time: O(n log n) Space: O(n)

Lưu ý <= trong merge: giữ stable sort. Khi buf[i] == buf[j], ưu tiên lấy element từ left half (đến trước trong input gốc). Đổi <= thành < vẫn sort đúng nhưng phá stability.

Lưu ý mid = lo + (hi - lo) / 2: tránh integer overflow khi lo + hi vượt giới hạn kiểu số nguyên. Cùng pitfall với binary search.

4.2 Trace ví dụ: sort [5, 2, 4, 6, 1, 3]

Ban đầu:   [5, 2, 4, 6, 1, 3]

Divide:
  trái:    [5, 2, 4]   phải: [6, 1, 3]

  chia nửa trái:
    [5, 2]    [4]
    [5] [2]

  Sort nửa trái:
    merge([5],[2])     -> [2, 5]
    merge([2,5],[4])   -> [2, 4, 5]

  chia nửa phải:
    [6, 1]    [3]
    [6] [1]

  Sort nửa phải:
    merge([6],[1])     -> [1, 6]
    merge([1,6],[3])   -> [1, 3, 6]

merge cuối ([2,4,5],[1,3,6]):
  so 2 vs 1  -> lấy 1  -> [1]
  so 2 vs 3  -> lấy 2  -> [1,2]
  so 4 vs 3  -> lấy 3  -> [1,2,3]
  so 4 vs 6  -> lấy 4  -> [1,2,3,4]
  so 5 vs 6  -> lấy 5  -> [1,2,3,4,5]
  nửa trái hết -> lấy 6  -> [1,2,3,4,5,6]

4.3 Bottom-up iterative

MergeSortBottomUp(A):
    n <- A.length
    buf <- mảng phụ kích thước n
    -- width = kích thước sub-array hiện tại: 1, 2, 4, 8, ...
    width <- 1
    while width < n:
        lo <- 0
        while lo < n - width:
            mid <- lo + width - 1
            hi  <- min(lo + 2*width - 1, n - 1)
            Merge(A, buf, lo, mid, hi)   -- cùng Merge() như trên
            lo <- lo + 2 * width
        width <- width * 2

Time: O(n log n) Space: O(n)

Iterative bottom-up tránh hoàn toàn recursion stack — bắt đầu merge từng cặp phần tử đơn lẻ, rồi merge từng cặp đoạn 2, đoạn 4, v.v. Cache access pattern hơi khác — bottom-up truy cập memory tuần tự hơn, đôi khi cache-friendlier.

5. Stable sort — cơ chế và ý nghĩa

Merge sort stable vì điều kiện <= trong merge step: khi hai phần tử bằng nhau (buf[i] == buf[j]), code chọn buf[i] từ left half trước. Left half đại diện cho các phần tử đến trước trong input gốc — nên thứ tự tương đối được bảo toàn.

Tại sao sort Object array mặc định dùng merge variant (TimSort)?

Sort Object nhận bất kỳ object nào với Comparator — comparator chỉ biết "A nhỏ hơn B hay không", không thể phân biệt hai object "bằng nhau" nhưng có identity khác nhau. Stability đảm bảo rằng khi sort theo secondary key, primary key order trong cùng nhóm được giữ nguyên.

-- Ví dụ: sort employees theo salary, rồi theo department
-- Mục tiêu: trong cùng department, giữ thứ tự salary từ bước 1

-- Bước 1: sort theo salary (stable)
-- [Alice:50k:Eng, Bob:30k:HR, Carol:50k:HR, Dave:30k:Eng]
-- -> [Bob:30k:HR, Dave:30k:Eng, Alice:50k:Eng, Carol:50k:HR]

-- Bước 2: sort theo department bằng STABLE sort
-- -> [Dave:30k:Eng, Alice:50k:Eng, Bob:30k:HR, Carol:50k:HR]
-- Trong Eng: Dave(30k) trước Alice(50k) -- giữ đúng thứ tự salary ✓
-- Trong HR: Bob(30k) trước Carol(50k)   -- giữ đúng thứ tự salary ✓

Sort mảng số nguyên nguyên thủy không cần stable vì primitive không có identity — hai số nguyên đều bằng 5 là hoàn toàn equivalent. Nên Dual-Pivot Quicksort (nhanh hơn, non-stable) được dùng.

6. K-way merge — generalize cho external sort

2-way merge (merge 2 sorted list) là trường hợp đặc biệt của k-way merge (merge k sorted list đồng thời).

KWayMerge(sortedLists[0..k-1]):
    -- MinHeap lưu (giá_trị, chỉ_số_list, vị_trí_trong_list)
    H <- MinHeap rỗng
    result <- []

    -- nạp phần tử đầu tiên từ mỗi list
    for i <- 0 đến k-1:
        if sortedLists[i] không rỗng:
            H.push((sortedLists[i][0], i, 0))

    while H không rỗng:
        (val, listIdx, pos) <- H.pop()    -- lấy giá trị nhỏ nhất
        result.append(val)
        -- đẩy phần tử tiếp theo từ cùng list
        if pos + 1 < sortedLists[listIdx].length:
            nextVal <- sortedLists[listIdx][pos + 1]
            H.push((nextVal, listIdx, pos + 1))

    return result

Time: O(n log k) Space: O(k)

Mỗi pop/push từ MinHeap tốn O(log k). Tổng n phần tử trên k list → O(n log k). Khi k nhỏ so với n (ví dụ k = 100 chunk, n = 100 triệu records), O(n log k) gần như O(n).

External sort pattern:

ExternalSort(file_100GB, RAM_16GB):
    -- Bước 1: chia thành k chunk vừa RAM
    chunks <- []
    for each chunk 8GB trong file:
        load chunk vào RAM
        sort chunk bằng in-memory sort
        ghi chunk đã sorted ra disk
        chunks.append(chunk_file)

    -- Bước 2: k-way merge từ k file sorted
    KWayMerge(chunks) -> output_file  -- chỉ cần k buffer nhỏ, không load toàn bộ

Peak RAM: một chunk (8GB) + k buffer nhỏ để đọc mỗi file. Với k = 13 chunks của 8GB, sort xong 100GB trên máy 16GB RAM.

Cross-link: Module 2 lesson 08 là mini-challenge implement external merge sort đầy đủ.

7. Pitfall tổng hợp

Pitfall 1 — Merge trực tiếp trên array gốc làm hỏng data

-- BUG: đọc và ghi cùng array trong khi merge
Merge_BUG(A, lo, mid, hi):
    i <- lo; j <- mid + 1; k <- lo
    while i <= mid và j <= hi:
        if A[i] <= A[j]:
            k <- k + 1; i <- i + 1    -- A[lo..k] là output, đang ghi đè A[i]
        else:
            A[k] <- A[j]              -- A[i] có thể đã bị ghi đè!
            k <- k + 1; j <- j + 1
    -- kết quả sai vì A[i] đã bị ghi đè trước khi đọc

Khi A[k] được ghi lên vị trí k đang nằm trong vùng left half (lo..mid), con trỏ i sau đó có thể đọc lại vị trí đó và nhận giá trị sai. Fix: sao chép lo..hi sang buffer trước, rồi merge từ buffer vào A.

Pitfall 2 — Integer overflow trong tính mid

-- BUG: lo + hi có thể tràn số khi cả hai đều lớn
mid <- (lo + hi) / 2     -- nếu lo = 1_000_000_000, hi = 1_500_000_000: tràn -> sai

-- ĐÚNG: tương đương nhưng an toàn
mid <- lo + (hi - lo) / 2

Khi lo + hi vượt giới hạn kiểu số nguyên, kết quả tràn thành số âm, mid thành âm, array index âm gây lỗi index out of bounds. Cùng pitfall trong binary search.

Pitfall 3 — <= vs < trong merge ảnh hưởng stability

-- STABLE: left-half thắng khi tie -- giữ thứ tự gốc
if buf[i] <= buf[j]:
    A[k] <- buf[i]; i <- i + 1

-- NON-STABLE: right-half thắng khi tie -- đảo thứ tự gốc với element bằng nhau
if buf[i] < buf[j]:
    A[k] <- buf[i]; i <- i + 1
-- else: right-half thắng

Cả hai đều cho kết quả sorted đúng, nhưng stability khác nhau. Nếu sort objects theo một field trong multi-key sort pipeline, dùng < thay vì <= sẽ phá vỡ thứ tự đã thiết lập từ bước sort trước.

8. Stable sort cho mảng số nguyên nguyên thủy

Sort mảng số nguyên nguyên thủy dùng Dual-Pivot Quicksort — non-stable. Với primitive, đây không thành vấn đề vì hai số nguyên bằng nhau là hoàn toàn equivalent.

Nhưng nếu bạn cần sort primitive array stable (ví dụ sort index array theo value của array khác), workaround là boxing sang Integer[] (hoặc kiểu object tương đương) để dùng TimSort (stable):

-- Workaround: box về kiểu object, sort stable, unbox
indices <- [0, 1, 2, ..., n-1]   -- mảng index
sort indices stable theo values[i]  -- sort index theo giá trị tương ứng
-- indices giờ chứa thứ tự index theo sorted order của values

Trade-off: boxing tốn khoảng 4x memory (object type tốn nhiều hơn primitive). Với mảng 10 triệu phần tử, tăng từ 40MB lên 160MB trên heap.

9. Ứng dụng thực tế

TimSort — merge variant cho Java và Python: Sort Object array mặc định dùng TimSort — Merge sort variant kết hợp với Insertion sort cho run ngắn (dưới 32 phần tử) và galloping mode khi một run áp đảo. Stable, O(n log n) worst case guaranteed, và khai thác partially-sorted data. Module 2 lesson 09 là case study sâu về TimSort internals.

External merge sort — PostgreSQL work_mem: Khi query ORDER BY trên dataset vượt work_mem (mặc định 4MB trong Postgres), Postgres spill sort xuống disk: chia thành các sorted run trên disk, sau đó k-way merge để tạo final sorted output. Tăng work_mem lên đủ lớn → sort hoàn toàn in-memory, loại bỏ disk I/O.

Lucene segment merge — search engine: Mỗi khi Lucene flush memory buffer ra disk, tạo ra một segment file (sorted list of terms). Khi nhiều segment nhỏ tích lũy, background merger dùng k-way merge để ghép các segment thành segment lớn hơn — tất cả đều sorted. Đây chính xác là cấu trúc của external merge sort, áp dụng ở scale của search index.

Spark / MapReduce shuffle phase: Sau map phase, các record cần được redistribute và sort theo key trước khi reduce. Spark sort từng partition (in-memory merge sort), sau đó merge các sorted partition khi reducer fetch data. Đây là distributed k-way merge ở scale cluster.

10. Deep Dive

11. Tóm tắt

• Recurrence T(n) = 2T(n/2) + n giải ra O(n log n): recursion tree có log₂ n level, mỗi level tổng work bằng n, tổng n log n.
• Best = average = worst = O(n log n): merge sort không adaptive — không có shortcut dù input đã sorted.
• Stable: điều kiện <= trong merge step ưu tiên left half khi tie, bảo toàn thứ tự tương đối.
• Space O(n): cần buffer phụ bằng kích thước input — không in-place.
• Bottom-up iterative tránh recursion stack, cùng complexity, đôi khi cache-friendlier.
• K-way merge với MinHeap: O(n log k) để merge k sorted list — nền tảng của external sort.
• Stable sort cho primitive: cần boxing sang kiểu object nếu cần stable sort cho số nguyên nguyên thủy.
• Ứng dụng: TimSort (Java/Python default), PostgreSQL external sort, Lucene segment merge, MapReduce shuffle.

12. Tự kiểm tra

Bài tiếp theo: Quick sort — pivot, partition, Dual-Pivot trong JDK