Sắp xếp & thứ tự

Sorting landscape — Comparison vs non-comparison, lower bound n log n

Vì sao Java dùng algorithm khác cho int[] và Integer[]? Vì sao comparison sort không thể nhanh hơn n log n nhưng Counting sort lại đạt O(n)? Bài này map toàn bộ landscape sorting — 9 algorithm, 5 thuộc tính phân loại, và nền tảng để đọc 7 lesson chi tiết tiếp theo.

Quadratic sorts — Bubble / Selection / Insertion và lý do TimSort vẫn dùng Insertion

Bubble sort dạy năm 1 rồi bỏ quên — nhưng TimSort (Java, Python) vẫn gọi Insertion sort cho subarray dưới 32 phần tử. Bài này so sánh 3 quadratic sort, code Java đầy đủ, benchmark thực tế, và giải thích vì sao Insertion sort adaptive và vẫn xuất hiện trong production library.

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

Sort 100GB log file trên máy 16GB RAM không thể dùng Quick sort — Merge sort chia để trị, luôn O(n log n), stable, và là nền tảng của external sort, TimSort, và Lucene segment merge. Bài này chứng minh T(n)=2T(n/2)+O(n) bằng recursion tree, code Java đầy đủ, và k-way merge cho external sort.

Quick sort — Pivot, partition, và Dual-Pivot trong JDK

Cùng O(n log n) với Merge sort nhưng nhanh hơn 30-40% trên random data — Quick sort thống trị primitive sort trong Java nhờ cache locality và zero buffer allocation. Bài này dạy partition mechanics (Lomuto vs Hoare), pivot strategies, Dual-Pivot Quicksort của Yaroslavskiy (Java 7+), và adversarial input kill quick sort thành O(n²).

Binary heap & Heapsort — Build-heap O(n) và priority queue backbone

Module 2 đã giới thiệu PriorityQueue qua API — bài này dive vào structure bên dưới: heap là complete binary tree lưu trong array, build-heap chạy O(n) (không phải O(n log n)), và heapsort kết hợp hai điều đó thành in-place sort O(n log n) guaranteed.

Counting / Radix / Bucket sort — Non-comparison O(n) khi key range nhỏ

Comparison sort bị chặn bởi lower bound n log n — nhưng Counting sort đạt O(n) mà không vi phạm. Bài này dạy 3 non-comparison sort: counting (range nhỏ), radix LSD/MSD (fixed-width key), bucket (uniform distribution), khi nào pick từng loại, và cảnh báo về memory cost.

Skip list — Probabilistic balanced, dễ implement hơn Red-Black tree

Red-Black tree đạt O(log n) guaranteed nhưng code rotation hàng trăm dòng. Skip list (Pugh 1990) đạt tương đương O(log n) expected với code chỉ ~50 dòng. Bài này dạy cấu trúc, probabilistic analysis, Java code đầy đủ, so sánh với RB tree, và lý do Redis ZSET chọn skip list.

Mini-challenge — External merge sort: sort 10GB file với 1GB RAM

Implement ExternalSorter: chia file thành sorted chunk, k-way merge bằng min-heap — pattern Postgres ORDER BY, Lucene segment merge, Hadoop shuffle đều dùng khi data vượt RAM.

Case Study: TimSort + Redis ZSET — 2 algorithm chiến thắng production

Module 4 đã đi qua 7 sorting algorithm + skip list. Production thực tế chỉ dùng 2 family: TimSort (Java Arrays.sort, Python sorted, Android, V8) và Skip list (Redis ZSET). Bài này dive source thật OpenJDK TimSort run detection + galloping merge và Redis ZSET skip list + dict — hiểu vì sao 2 quyết định này thắng mọi alternative trong real workload.