Module 2 — Sắp xếp & thứ tự: tổng quan

TL;DR: Module 2 xây dựng hiểu biết toàn diện về sắp xếp — từ vì sao mọi comparison sort đều bị chặn ở Ω(n log n), cách non-comparison sort (Counting/Radix/Bucket) phá vỡ giới hạn đó, đến tại sao production hội tụ về TimSort cho in-memory và Skip list cho sorted set. Bạn sẽ implement được merge sort, quick sort, heap sort từ đầu, phân tích tradeoff, thiết kế external merge sort cho file vượt RAM, và đọc được source OpenJDK TimSort + Redis ZSET.

Vì sao module này tồn tại

Sắp xếp là bài toán nền tảng nhất của khoa học máy tính — xuất hiện trong mọi layer từ OS scheduler đến database index đến UI table. Nhưng "gọi built-in sort" chưa đủ nếu bạn cần debug hiệu năng, chọn algorithm đúng cho dữ liệu cụ thể, hoặc thiết kế hệ thống xử lý dữ liệu lớn hơn RAM.

Module này trả lời ba nhóm câu hỏi mà developer thực tế hay gặp:

• Tại sao Java dùng hai algorithm khác nhau cho int[] và Integer[]? Câu trả lời liên quan đến stability, cache behavior, và tradeoff giữa primitive vs object sort.
• Khi nào gọi Counting sort thay vì Quick sort? Câu trả lời là lý thuyết cận dưới Ω(n log n) — hiểu nó, bạn biết khi nào non-comparison sort hợp lệ.
• Sắp xếp 10GB file trên máy có 1GB RAM? External merge sort — thiết kế có cấu trúc, không phải "đọc từng dòng".

Sau module này bạn sẽ

• Compare các thuật toán sắp xếp theo time / space / stability và chọn đúng theo dữ liệu
• Explain cận dưới Ω(n log n) của comparison sort và khi nào non-comparison sort vượt qua được
• Implement merge sort, quick sort, heap sort và phân tích best / average / worst case
• Design sắp xếp cho dữ liệu vượt RAM (external merge sort) và hiểu adaptive sort (TimSort)

Bản đồ module

flowchart LR
    A["00\nTổng quan"] --> B["01\nSort\nlandscape"]
    B --> C["02\nQuadratic\nsorts"]
    C --> D["03\nMerge\nsort"]
    D --> E["04\nQuick\nsort"]
    E --> F["05\nHeap &\nHeapsort"]
    F --> G["06\nCounting\nRadix Bucket"]
    G --> H["07\nSkip list"]
    H --> I["08\nExternal\nmerge sort"]
    I --> J["09\nCase study\nTimSort & ZSET"]
    J --> K["10\nTổng kết"]

Lộ trình module

Thứ tự bài được thiết kế theo nguyên tắc "landscape trước, cơ chế sau":

Bài 01 — Sort landscape mở đầu bằng bản đồ tổng thể: comparison vs non-comparison sort, 5 thuộc tính phân loại (stable, in-place, adaptive, online, comparison-based), và tại sao lower bound Θ(n log n) là bất khả vượt qua đối với comparison sort. Đọc bài này trước — mọi bài sau sẽ có context để đặt vào.

Bài 02 — Quadratic sorts đào sâu Insertion sort, Selection sort, Bubble sort: ba algorithm O(n²) tưởng chừng chỉ dùng để dạy, nhưng Insertion sort thực ra là building block của TimSort và hiệu quả trên nearly-sorted data.

Bài 03 — Merge sort là algorithm đầu tiên đạt O(n log n) guaranteed: divide-conquer, merge stable, phân tích recurrence T(n) = 2T(n/2) + O(n), k-way merge và external sort pattern. Nền tảng cơ chế merge cho TimSort.

Bài 04 — Quick sort là algorithm nhanh nhất trong thực tế với average-case O(n log n) và constant factor thấp: partition scheme (Lomuto vs Hoare), pivot selection, worst case O(n²) khi pivot tệ và cách tránh (randomized/median-of-three), và tại sao Quick sort nhanh hơn Merge sort trên practice dù cùng big-O.

Bài 05 — Heap & Heapsort kết hợp hai bài: cấu trúc dữ liệu Heap (binary heap, heapify, priority queue) và Heapsort dùng heap để sort in-place O(n log n) guaranteed — không cần extra space như Merge sort, không có worst case như Quick sort.

Bài 06 — Counting, Radix, Bucket sort phá vỡ giới hạn Ω(n log n): ba algorithm không so sánh phần tử trực tiếp, đạt O(n+k) hay O(nk) khi key có range hữu hạn. Hiểu khi nào đây là lựa chọn đúng — và khi nào không.

Bài 07 — Skip list là cấu trúc dữ liệu probabilistic cho sorted set: tìm kiếm O(log n) trung bình, không cần rotation như BST, đơn giản implement hơn balanced BST. Nền tảng cho bài case study Redis ZSET.

Bài 08 — Mini-challenge: External merge sort là bài thực hành thiết kế: sort file 10GB trên máy 1GB RAM. Không có "đáp án có sẵn" — bạn phải áp dụng merge sort + bounded memory để thiết kế giải pháp.

Bài 09 — Case study: TimSort + Redis ZSET là đỉnh module: dive source OpenJDK TimSort (run detection, galloping merge, merge stack invariant) và Redis ZSET (skip list + dict dual structure, trường span cho ZRANK O(log n)). Hiểu tại sao hai quyết định này thắng mọi alternative trong production.

Bài 10 — Tổng kết gom cheat sheet, glossary, pitfall và self-assessment toàn module.

Yêu cầu trước khi bắt đầu

• Đã hoàn thành Module 1 — Tìm kiếm nhanh (đặc biệt Binary search và BST — module này mở rộng sang heap và skip list).
• Biết ký hiệu Big-O cơ bản (O, Ω, Θ) — Thuật toán Căn bản — Module 1 đã cover.
• Pseudocode track thuật toán: keyword điều khiển English (if, while, for), identifier English, chú thích tiếng Việt có dấu.

Time budget

Cách học module này hiệu quả

• Bắt đầu từ bài 01 — Sort landscape. Đừng nhảy thẳng vào Quick sort. Bức tranh tổng thể quyết định bạn học bài chi tiết theo context nào.
• Tự implement trước khi đọc pseudocode. Đặc biệt với Merge sort và Quick sort — viết pseudocode từ ý tưởng "divide-and-conquer", sau đó đối chiếu với bài.
• Ghi nhớ WHY, không chỉ complexity. Tại sao Quick sort nhanh hơn Merge sort trên thực tế dù cùng O(n log n)? Tại sao Heap sort ít dùng dù O(n log n) guaranteed? Những câu hỏi này quan trọng hơn việc thuộc bảng complexity.
• Bài 08 là bài thực hành — đừng skip. External merge sort là pattern thực tế cho pipeline xử lý data lớn. Tự thiết kế trước khi đọc solution.
• Bài 09 đọc song song với source code. Mở java.util.TimSort.java trên GitHub trong khi đọc — thấy code thật giúp anchor lý thuyết.

Bài tiếp theo: Sort landscape