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

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 (Java Arrays.parallelSort), k-way merge (Lucene segment merge), và TimSort (merge step của Java Arrays.sort(Object[])).

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, code Java đầ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)

Với 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)

Giải recurrence này trong section tiếp theo.

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, each work n/2^k     work = 2^k × n/2^k = n
         ...
Level log₂n: n nodes, each 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.

4. Code Java đầy đủ

4.1 Top-down recursive

public static void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int[] buf = new int[arr.length]; // allocate buffer once, reuse across all merge calls
    sort(arr, buf, 0, arr.length - 1);
}

private static void sort(int[] arr, int[] buf, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2; // avoid overflow: NOT (lo + hi) / 2
    sort(arr, buf, lo, mid);
    sort(arr, buf, mid + 1, hi);
    merge(arr, buf, lo, mid, hi);
}

private static void merge(int[] arr, int[] buf, int lo, int mid, int hi) {
    // copy segment to buf first so we can read from buf while writing to arr
    for (int i = lo; i <= hi; i++) buf[i] = arr[i];

    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (buf[i] <= buf[j]) arr[k++] = buf[i++]; // <= keeps sort STABLE
        else                  arr[k++] = buf[j++];
    }
    while (i <= mid) arr[k++] = buf[i++]; // copy remaining left half
    // right half already in arr -- no copy needed
}

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 — element bằng nhau từ right half sẽ đứng trước left half trong output.

Lưu ý mid = lo + (hi - lo) / 2: tránh integer overflow khi lo + hi vượt Integer.MAX_VALUE. Cùng pitfall với binary search — xem Module 3 lesson 04.

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

Initial:   [5, 2, 4, 6, 1, 3]

Divide:
  left:    [5, 2, 4]   right: [6, 1, 3]

  left half divide:
    [5, 2]    [4]
    [5] [2]

  Sort left half:
    merge([5],[2])     -> [2, 5]
    merge([2,5],[4])   -> [2, 4, 5]

  right half divide:
    [6, 1]    [3]
    [6] [1]

  Sort right half:
    merge([6],[1])     -> [1, 6]
    merge([1,6],[3])   -> [1, 3, 6]

Final merge([2,4,5],[1,3,6]):
  compare 2 vs 1  -> take 1  -> [1]
  compare 2 vs 3  -> take 2  -> [1,2]
  compare 4 vs 3  -> take 3  -> [1,2,3]
  compare 4 vs 6  -> take 4  -> [1,2,3,4]
  compare 5 vs 6  -> take 5  -> [1,2,3,4,5]
  left exhausted  -> take 6  -> [1,2,3,4,5,6]

4.3 Bottom-up iterative

public static void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    int[] buf = new int[n];
    // width = current subarray size: 1, 2, 4, 8, ...
    for (int width = 1; width < n; width *= 2) {
        for (int lo = 0; lo < n - width; lo += 2 * width) {
            int mid = lo + width - 1;
            int hi  = Math.min(lo + 2 * width - 1, n - 1);
            merge(arr, buf, lo, mid, hi); // same merge() as above
        }
    }
}

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. Complexity giống top-down: O(n log n) time, O(n) space. Cache access pattern hơi khác — bottom-up truy cập memory tuần tự hơn, đôi khi cache-friendlier.

Khi nào dùng iterative thay top-down? Khi recursion stack là mối lo: ví dụ Comparator object kích hoạt extra method call trong mỗi recursive frame, hoặc khi cần predictable stack usage trong embedded context. Với n thông thường, depth = log₂(10M) khoảng 23 level — quá nông để gây StackOverflowError, nên đây không phải lý do chính trong Java production thông thường.

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 Java Arrays.sort(Object[]) dùng merge variant (TimSort)?

Arrays.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.

// Example: sort employees by salary, then by department
// Goal: within same department, preserve salary order
employees.sort(Comparator.comparingInt(Employee::getSalary));     // step 1
employees.sort(Comparator.comparing(Employee::getDepartment));    // step 2 -- must be stable
// => within same department, salary order preserved (stable merge sort)

Arrays.sort(int[]) primitive không cần stable vì primitive không có identity — hai int đều bằng 5 là hoàn toàn equivalent, không thể phân biệt. 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).

Cách dùng PriorityQueue cho k-way merge:

// k-way merge: merge k sorted lists into one sorted output
// Each element in PQ: (value, listIndex, positionInList)
public static List<Integer> kWayMerge(List<List<Integer>> sortedLists) {
    // min-heap by value
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    List<Integer> result = new ArrayList<>();

    // seed PQ with first element from each list
    for (int i = 0; i < sortedLists.size(); i++) {
        if (!sortedLists.get(i).isEmpty()) {
            pq.offer(new int[]{sortedLists.get(i).get(0), i, 0});
        }
    }

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int val = top[0], listIdx = top[1], pos = top[2];
        result.add(val);
        // push next element from same list
        if (pos + 1 < sortedLists.get(listIdx).size()) {
            pq.offer(new int[]{sortedLists.get(listIdx).get(pos + 1), listIdx, pos + 1});
        }
    }
    return result;
}

Complexity: mỗi poll/offer từ PriorityQueue 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 = 100M records), O(n log k) gần như O(n).

External sort pattern:

1. Chia 100GB file thành các chunk 8GB (vừa RAM).
2. Load từng chunk, sort bằng in-memory sort (Quick sort hoặc Merge sort), ghi ra k file sorted trên disk.
3. Mở k file sorted đồng thời, dùng k-way merge với PriorityQueue.
4. Write output sorted ra file kết quả theo stream — không cần load toàn bộ lên RAM.

Peak RAM usage: 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 4 lesson 08 là mini-challenge implement external merge sort đầy đủ.

7. Pitfall tổng hợp

Pitfall 1 — Forget buffer copy: merge trực tiếp trên array gốc corrupt data

// WRONG: reading and writing same array concurrently during merge
private static void mergeBroken(int[] arr, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) { k++; i++; }  // arr[lo..k] is output, overwriting arr[i]
        else { arr[k++] = arr[j++]; }         // arr[i] may already be overwritten!
    }
}

Khi arr[k++] = arr[j++] 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: copy lo..hi sang buffer trước, rồi merge từ buffer vào arr — như trong code đúng ở section 4.

In-place merge sort tồn tại nhưng phức tạp (dùng rotation O(n²) hoặc các thuật toán đặc biệt) và thực tế chậm hơn đáng kể. Không dùng trong production.

Pitfall 2 — Integer overflow trong tính mid

// WRONG: lo + hi can overflow when both are large
int mid = (lo + hi) / 2;  // if lo = 1_000_000_000, hi = 1_500_000_000: overflow -> negative

// CORRECT: equivalent but overflow-safe
int mid = lo + (hi - lo) / 2;

lo + hi vượt Integer.MAX_VALUE (khoảng 2.1 tỷ) khi cả hai đều lớn — kết quả wrap thành số âm, mid thành âm, array index âm gây ArrayIndexOutOfBoundsException. Cùng pitfall trong binary search.

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

// STABLE: left-half element wins on tie -- preserves original order
if (buf[i] <= buf[j]) arr[k++] = buf[i++];

// NON-STABLE: right-half element wins on tie -- reverses original order for equal elements
if (buf[i] < buf[j]) arr[k++] = buf[i++];
// else right-half wins: arr[k++] = buf[j++]

Cả hai đều cho kết quả sorted đúng, nhưng stability khác nhau. Nếu bạn 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 int[] Java không tồn tại

Arrays.sort(int[]) dùng Dual-Pivot Quicksort — non-stable. Với primitive, đây không thành vấn đề vì hai int 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[]:

int[] values = {5, 3, 1, 3, 2};

// Workaround: box to Integer[], sort stable (TimSort), unbox
Integer[] boxed = new Integer[values.length];
for (int i = 0; i < values.length; i++) boxed[i] = values[i];
Arrays.sort(boxed);  // TimSort -- stable
// unbox back if needed

// Alternative: sort index array by value -- useful when you need original positions
Integer[] indices = new Integer[values.length];
for (int i = 0; i < indices.length; i++) indices[i] = i;
Arrays.sort(indices, Comparator.comparingInt(i -> values[i]));  // stable, sort indices by value
// indices now: [2, 4, 1, 3, 0] -- positions of values in sorted order

Trade-off: boxing int sang Integer tốn khoảng 4x memory (16 bytes per Integer object thay vì 4 bytes per int). 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: Arrays.sort(Object[]) trong Java 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 4 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. Module 4 lesson 08 mini-challenge implement external sort.

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 PriorityQueue: O(n log k) để merge k sorted list — nền tảng của external sort.
• Arrays.sort(int[]) không stable: dùng Integer[] với boxing nếu cần stable sort cho primitive.
• Ứ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, JDK Dual-Pivot