Module 2 — Tổng kết & cheat sheet

TL;DR: Module 2 đào sâu toàn bộ landscape sorting — từ cận dưới lý thuyết Ω(n log n) của comparison sort, qua implement Merge/Quick/Heap sort từ đầu, đến thiết kế external merge sort cho dữ liệu vượt RAM và đọc source TimSort + Redis ZSET. Trang này là cheat sheet để bookmark: bảng so sánh 9 algorithm, glossary 15 thuật ngữ, 5 pitfall thực tế, và self-assessment để tự kiểm tra mức độ đạt module.

Đã đi qua những gì

Bạn bắt đầu từ bài 00 — Tổng quan module: tại sao sort quan trọng hơn "gọi built-in", và bản đồ 9 bài của module.

Bài 01 — Sort landscape map toàn cảnh: 9 algorithm, 5 thuộc tính phân loại (stable, in-place, adaptive, online, comparison-based), và bằng chứng cây quyết định chứng minh cận dưới Ω(n log n) cho mọi comparison sort. Bài này cũng giải thích tại sao Java dùng Dual-Pivot Quicksort cho int[] và TimSort cho Integer[].

Bài 02 — Quadratic sorts đào sâu Insertion sort O(n²) worst case nhưng O(n) khi nearly-sorted — lý do nó là building block của TimSort và Shell sort. Selection sort bất biến O(n²), Bubble sort chỉ có giá trị dạy khái niệm stable swap.

Bài 03 — Merge sort đầu tiên đạt O(n log n) guaranteed mọi case: divide-conquer, merge stable giữ thứ tự tương đối, phân tích recurrence T(n) = 2T(n/2) + O(n) ra O(n log n). Space O(n) là nhược điểm chính. K-way merge mở rộng thành external sort pattern.

Bài 04 — Quick sort nhanh nhất trên thực tế: partition đặt pivot vào đúng vị trí, recursion hai half. Average O(n log n) với constant factor thấp hơn Merge sort nhờ cache-friendly access. Worst case O(n²) khi pivot luôn cực đoan — tránh bằng randomized pivot hoặc median-of-three.

Bài 05 — Heap & Heapsort kết hợp cấu trúc dữ liệu (binary heap, heapify O(n), priority queue operations O(log n)) và Heapsort: build heap + extract-max n lần, tổng O(n log n) in-place, không worst case như Quick sort nhưng cache-unfriendly hơn.

Bài 06 — Counting, Radix, Bucket sort phá vỡ Ω(n log n): không so sánh cặp phần tử — thay vào đó dùng thông tin về key range. Counting sort O(n+k) cho integer nhỏ, Radix sort O(nk) cho integer nhiều chữ số, Bucket sort O(n) average cho dữ liệu phân phối đều. Giới hạn: chỉ áp dụng khi key có cấu trúc.

Bài 07 — Skip list là cấu trúc dữ liệu probabilistic cho sorted set: tower của linked list nhiều tầng, search/insert/delete O(log n) average không cần rotation. Đơn giản implement hơn balanced BST — nền tảng Redis ZSET.

Bài 08 — Mini-challenge: External merge sort là bài thực hành: sort file vượt RAM bằng k-way merge — chia file thành chunk vừa RAM, sort từng chunk, merge k chunk song song bằng min-heap. Pattern này xuất hiện trong Hadoop MapReduce, database external sort, và log processing pipeline.

Bài 09 — Case study: TimSort + Redis ZSET là đỉnh module: TimSort detect run (đoạn đã sorted), extend bằng insertion sort đến min_run, galloping merge khi một run dài hơn hẳn, và merge stack invariant đảm bảo O(n log n) worst case. Redis ZSET kết hợp skip list (range scan O(log n)) + dict (point lookup O(1)) + trường span cho ZRANK O(log n).

🗺️ Cheat sheet

Bảng so sánh 9 thuật toán sắp xếp

*Bucket sort stable khi dùng stable sort bên trong mỗi bucket.

Quy tắc chọn algorithm

flowchart TD
    START["Bài toán sort"] --> Q1{"Key có cấu trúc?\n(integer, string ngắn)"}
    Q1 -->|"Có, range k nhỏ"| COUNTING["Counting sort\nO(n+k)"]
    Q1 -->|"Có, nhiều chữ số"| RADIX["Radix sort\nO(nk)"]
    Q1 -->|"Phân phối đều"| BUCKET["Bucket sort\nO(n) avg"]
    Q1 -->|"Không / không biết"| Q2{"Cần stable?"}
    Q2 -->|"Có"| Q3{"Bộ nhớ extra OK?"}
    Q3 -->|"Có"| MERGE["Merge sort\nO(n log n), O(n)"]
    Q3 -->|"Không"| TIMSORT["TimSort\nO(n log n), O(log n)"]
    Q2 -->|"Không"| Q4{"Dữ liệu vượt RAM?"}
    Q4 -->|"Có"| EXTERNAL["External merge sort\nk-way merge"]
    Q4 -->|"Không"| QUICK["Quick sort\nO(n log n) avg"]

External merge sort — skeleton

function externalMergeSort(inputFile, outputFile, chunkSize):
    -- Pha 1: Tạo sorted run
    chunks <- []
    while inputFile không hết:
        data <- đọc chunkSize phần tử vào RAM
        sort(data)                         -- bất kỳ in-memory sort
        chunkFile <- ghi data ra file tạm
        chunks.append(chunkFile)

    -- Pha 2: k-way merge
    H <- MinHeap                           -- mỗi entry: (giá trị, chunk_index)
    for each chunk trong chunks:
        H.push((chunk.readNext(), chunk))  -- lấy phần tử đầu mỗi chunk
    while H không rỗng:
        (val, chunk) <- H.pop()
        ghi val ra outputFile
        if chunk còn phần tử:
            H.push((chunk.readNext(), chunk))

// Time: O(n log n)  Space: O(k) RAM cho heap, n/k cho mỗi chunk buffer

📖 Glossary module

⚠️ Pitfall tổng hợp

Pitfall 1 — Dùng Counting sort khi k quá lớn. Counting sort O(n+k) hiệu quả khi k (range của key) nhỏ so với n. Nếu sort 1000 số nguyên trong range [0, 10^9], array count cần 10^9 ô — tốn 4GB RAM. Rule: dùng Counting sort khi k = O(n). Nếu k lớn, chuyển sang Radix sort (chia key thành chữ số nhỏ hơn).

Pitfall 2 — Quick sort với input sorted hoặc nearly-sorted. Naive Quick sort (pivot = first element) trên sorted array tạo worst case O(n²): mỗi partition chia 0 và n-1. Gặp nhiều trong thực tế khi sort log file đã có timestamp tăng dần. Fix: randomized pivot hoặc median-of-three. Arrays.sort(int[]) của Java dùng Dual-Pivot Quicksort với các heuristic này.

Pitfall 3 — Nhầm stable sort với in-place sort. Heap sort in-place nhưng không stable. Merge sort stable nhưng không in-place (cần O(n) buffer). Quick sort không stable (swap có thể đảo thứ tự equal elements) và không guaranteed in-place (đệ quy O(log n) stack). Khi sort object theo nhiều key lần lượt (sort by date, rồi sort by name), cần stable sort để giữ thứ tự date trong cùng nhóm name.

Pitfall 4 — External merge sort không kiểm soát số file descriptor. Nếu k-way merge mở quá nhiều chunk file đồng thời, OS giới hạn file descriptor (mặc định 1024 trên Linux) sẽ báo lỗi. Fix: giới hạn số chunk mỗi lần merge (ví dụ k=256), sau đó merge nhiều round cho đến khi còn 1 file. Đây là k-way merge nhiều tầng — complexity vẫn O(n log n).

Pitfall 5 — Dùng Java Arrays.sort(Integer[]) cho primitive-heavy workload. Arrays.sort(Integer[]) dùng TimSort, stable nhưng tốn autoboxing mỗi lần so sánh. Arrays.sort(int[]) dùng Dual-Pivot Quicksort trực tiếp trên primitive — nhanh hơn đáng kể (2-3x) khi n lớn. Nếu cần stable sort trên primitive, cách duy nhất là implement Merge sort thủ công.

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• So sánh được ít nhất 5 thuật toán sắp xếp theo time / space / stability — giải thích khi nào chọn Quick sort thay Merge sort, và khi nào Counting sort vượt qua cả hai.
  • Nếu chưa: đọc lại bài 01 (sort landscape, bảng so sánh) và bài 06 (counting/radix/bucket).
• Giải thích được cận dưới Ω(n log n) của comparison sort bằng cây quyết định — và chỉ ra điều kiện để non-comparison sort phá được giới hạn đó.
  • Nếu chưa: đọc lại bài 01 (mục "Cận dưới n log n — bằng chứng cây quyết định").
• Implement được merge sort và quick sort bằng pseudocode — ghi rõ best / average / worst case và giải thích nguyên nhân worst case.
  • Nếu chưa: đọc lại bài 03 (merge sort) và bài 04 (quick sort, mục partition + worst case).
• Thiết kế được external merge sort cho file vượt RAM — mô tả hai pha (tạo sorted run + k-way merge) và giải thích tại sao TimSort tốt hơn Merge sort thuần trên dữ liệu thực tế.
  • Nếu chưa: làm lại bài 08 (mini-challenge) và đọc bài 09 (TimSort run detection + galloping).

🚀 What's next

Module 2 cho bạn nền tảng vững về sorting — từ lý thuyết Ω(n log n) đến implementation đến production case study. Module 3 — Đồ thị mở ra một chiều khác: dữ liệu không còn là dãy tuyến tính mà là mạng lưới quan hệ. BFS/DFS để traversal, Dijkstra/Bellman-Ford cho shortest path, Kruskal/Prim cho minimum spanning tree, topological sort cho dependency resolution. Những algorithm này xuất hiện trong routing protocol, build system, recommendation engine, và social graph — mọi nơi có "mối liên hệ" giữa các thực thể.

Bài tiếp theo: Module 3 — Đường đi & quan hệ: tổng quan

📚 Tài liệu mở rộng

• Sách: Introduction to Algorithms (CLRS) — Chapters 6 (Heapsort), 7 (Quicksort), 8 (Sorting in Linear Time). Bản chứng minh formal nhất của cận dưới comparison sort (Chapter 8.1).
• Sách: Algorithm Design — Kleinberg & Tardos. Chapter 5 (Divide and Conquer) có phân tích Merge sort recurrence rất rõ.
• Source code: OpenJDK TimSort.java — đọc song song với bài 09, chú ý method mergeCollapse() implement merge stack invariant.
• Paper: Tim Peters — listsort.txt — tài liệu gốc của Tim Peters mô tả thiết kế TimSort cho Python. Dài nhưng rất readable.
• Source code: Redis t_zset.c — implementation ZSET, tìm hàm zslInsert, zslGetRank để thấy trường span dùng thế nào.
• Blog: Sorting Algorithms Visualized — animation từng bước cho mọi algorithm trong module, tốt để kiểm tra hiểu biết trực giác.