Sắp xếp & thứ tự

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

9 sorting algorithm: time/space/stability, cận dưới n log n, external merge sort cho dữ liệu vượt RAM, case study TimSort + Redis ZSET.

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

Vì sao Java sort int[] và Integer[] khác nhau? Comparison sort bị chặn n log n nhưng Counting sort đạt O(n) — bài này map 9 algorithm, 5 thuộc tính phân loại.

Quadratic sorts — Bubble, Selection, Insertion sort

TimSort dùng Insertion sort cho subarray nhỏ — so sánh Bubble, Selection, Insertion, pseudocode, benchmark, lý do Insertion sort adaptive vẫn có trong production library.

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

Sort 100GB log trên 16GB RAM cần Merge sort — luôn O(n log n), stable, nền tảng external sort và TimSort. Chứng minh T(n)=2T(n/2)+O(n) qua recursion tree, k-way merge.

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

Quick sort nhanh hơn Merge sort 30-40% trên random data nhờ cache locality. Partition Lomuto vs Hoare, Dual-Pivot Quicksort (Java 7+), adversarial input khiến O(n²).

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

Heap là complete binary tree trong array; build-heap chạy O(n). Heapsort cho in-place O(n log n) guaranteed, nền tảng PriorityQueue và top-K pattern.

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

Counting sort đạt O(n) mà không vi phạm lower bound n log n — 3 non-comparison sort: counting, radix LSD/MSD, bucket; khi nào chọn từng loại và memory cost cần lưu ý.

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

Skip list đạt O(log n) với ~50 dòng code, dễ hơn Red-Black tree. Probabilistic analysis, pseudocode, so sánh RB tree, 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 rồi k-way merge bằng min-heap — pattern Postgres ORDER BY, Lucene, Hadoop shuffle dùng khi data vượt RAM.

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

Hai family thống trị production: TimSort (Java, Python, V8) và Skip list (Redis ZSET). Dive source OpenJDK run detection, galloping merge, Redis ZSET skip list + dict.

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

Recap sắp xếp & thứ tự: bảng so sánh time/space/stability 9 algorithm, glossary, 5 pitfall, self-assessment 4 câu khớp learning outcomes.