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

TL;DR: Sorting algorithm chia làm hai nhóm lớn: comparison sort (chỉ so sánh từng cặp phần tử, lower bound Θ(n log n) là bất khả vượt qua) và non-comparison sort (dùng thông tin về key range để đặt thẳng vào vị trí, đạt O(n+k)). Năm thuộc tính phân loại — stable, in-place, adaptive, online, comparison-based — quyết định algorithm nào phù hợp với bài toán nào. Không có algorithm nào thắng cả 5. Java dùng Dual-Pivot Quicksort cho int[] (nhanh, non-stable) và TimSort cho Integer[] (stable, adaptive) — hai quyết định có lý do rõ ràng.

Thử bài toán kinh điển: sắp xếp 1 triệu số nguyên. Junior viết Bubble sort O(n²) — chạy khoảng 1 phút trên laptop thông thường. Senior gọi built-in sort — chạy dưới 50ms. Nhanh hơn 1200 lần.

Nhưng câu hỏi thú vị không phải "dùng hàm có sẵn nhanh hơn tự viết". Câu hỏi là: vì sao lower bound của mọi comparison sort là n log n trong khi Counting sort lại đạt O(n)? Và tại sao Quick sort thực tế nhanh hơn Merge sort dù cùng độ phức tạp trung bình?

Bài này map landscape các sorting algorithm — comparison vs non-comparison, stable vs in-place, adaptive — đặt nền cho 8 lesson tiếp theo của Module 2 (bài 02–09).

1. Analogy — Sắp bài tú lơ khơ

Hình dung bạn đang sắp lại một bộ bài 52 lá theo thứ tự.

Cách 1 — Comparison sort: cầm 2 quân bài, so sánh, đặt lá nhỏ hơn sang trái. Lặp lại cho đến khi xong. Mỗi cặp đặt cạnh nhau là 1 phép so sánh. Bạn không cần biết trước tập giá trị gồm những lá nào — chỉ cần biết "lá này lớn hơn hay nhỏ hơn lá kia". Merge sort, Quick sort, Heap sort đều thuộc nhóm này.

Cách 2 — Non-comparison sort: chia sẵn 4 ô theo suit (cơ, rô, nhép, bích), rồi đặt thẳng mỗi lá vào ô tương ứng mà không cần so sánh lá nào với lá nào. Nhanh hơn vì bạn dùng thông tin về key range — biết trước chỉ có 52 lá, biết trước 4 suit. Counting sort và Radix sort thuộc nhóm này.

2. Năm thuộc tính phân loại sorting algorithm

Trước khi chọn sorting algorithm cho một bài toán cụ thể, cần hiểu 5 thuộc tính này:

Không có algorithm nào thắng cả 5 — đây là lý do tồn tại nhiều algorithm khác nhau và tại sao Java dùng algorithm khác nhau cho từng use case.

3. Comparison sort lower bound — vì sao không thể nhanh hơn n log n

Đây là kết quả lý thuyết quan trọng nhất trong sorting: không có comparison sort nào có worst-case tốt hơn O(n log n).

3.1 Decision tree argument

Mỗi lần so sánh hai element là một nhánh quyết định nhị phân: "element A nhỏ hơn B?" → yes hoặc no. Toàn bộ quá trình sort là một cây nhị phân các quyết định này (gọi là decision tree).

Với n element, có n! cách sắp xếp khả dĩ (permutation). Để sort đúng mọi input, thuật toán phải có khả năng phân biệt tất cả n! permutation — mỗi leaf của decision tree phải tương ứng với đúng một permutation.

n = 3, n! = 6 permutation: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

                 A[0] < A[1]?
                /            \
          yes                  no
       A[1] < A[2]?          A[0] < A[2]?
       /         \            /          \
    [1,2,3]  A[0]<A[2]?  [2,1,3]    A[1]<A[2]?
              /    \                  /       \
         [1,3,2] [3,1,2]         [2,3,1]  [3,2,1]

Cây nhị phân có n! leaf phải có chiều cao tối thiểu là log₂(n!). Theo xấp xỉ Stirling:

log₂(n!) = Θ(n log n)

Hệ quả: mọi comparison sort phải thực hiện ít nhất Θ(n log n) phép so sánh trong worst case. Không có cách nào tốt hơn khi chỉ dùng so sánh.

graph TD
    ROOT["A[0] < A[1]?"]
    L1["A[1] < A[2]?"]
    R1["A[0] < A[2]?"]
    LL["[1,2,3]"]
    LR["A[0] < A[2]?"]
    RL["[2,1,3]"]
    RR["A[1] < A[2]?"]
    LRL["[1,3,2]"]
    LRR["[3,1,2]"]
    RRL["[2,3,1]"]
    RRR["[3,2,1]"]

    ROOT -- "có" --> L1
    ROOT -- "không" --> R1
    L1 -- "có" --> LL
    L1 -- "không" --> LR
    R1 -- "có" --> RL
    R1 -- "không" --> RR
    LR -- "có" --> LRL
    LR -- "không" --> LRR
    RR -- "có" --> RRL
    RR -- "không" --> RRR

3.2 Non-comparison sort bypass bằng cách nào?

Counting sort và Radix sort không so sánh element với nhau — thay vào đó dùng thông tin về key range:

-- Counting sort: biết key nằm trong [0, k)
count[v] <- 0 cho mọi v trong [0, k)
for each phần tử x trong A:
    count[x] <- count[x] + 1         -- đếm tần suất
-- tính prefix sum để biết vị trí đặt
for v <- 1 đến k-1:
    count[v] <- count[v] + count[v-1]
-- đặt thẳng vào vị trí đúng -- không một phép so sánh nào
for i <- n-1 xuống 0:
    output[count[A[i]] - 1] <- A[i]
    count[A[i]] <- count[A[i]] - 1

Time: O(n+k) Space: O(n+k)

Decision tree argument không áp dụng vì không có "nhánh so sánh" — chỉ có index arithmetic.

4. Module 2 roadmap — 9 algorithm

Bảng dưới đây là bản đồ toàn bộ Module 2. Cột complexity: n log n là O(n log n), n+k là O(n+k):

Ghi chú: k = key range, d = số digit. Quick sort Space là O(log n) recursion stack, không phải O(1) thực sự — nhưng thường được coi là "in-place" vì không dùng buffer phụ bằng kích thước input.

*Skip list là cấu trúc dữ liệu sorted set (không phải sorting algorithm cho mảng): insert/delete/search đều O(log n) per operation, duy trì thứ tự tự động. Cột complexity ở trên phản ánh cost để xây dựng sorted set từ n phần tử. Không dùng skip list để sort mảng thông thường — dùng Merge/Quick/Heap sort. Lesson 07 deep dive skip list internals và Redis ZSET.

graph TD
    ROOT["Sorting Algorithm"]
    CMP["Comparison-based<br/>lower bound Θ(n log n)"]
    NCMP["Non-comparison<br/>dùng key range"]
    Q["Quadratic O(n²)<br/>Bubble / Selection / Insertion"]
    NLN["O(n log n)<br/>Merge / Quick / Heap"]
    CNT["Counting Sort<br/>O(n+k)"]
    RAD["Radix Sort<br/>O(n×d)"]

    ROOT --> CMP
    ROOT --> NCMP
    CMP --> Q
    CMP --> NLN
    NCMP --> CNT
    NCMP --> RAD

5. Stable sort — vì sao quan trọng

Stable sort giữ nguyên thứ tự tương đối của các element có giá trị bằng nhau.

Use case cụ thể: bạn có danh sách nhân viên đã được sort theo tên (A-Z). Bây giờ cần sort lại theo mức lương. Nếu dùng stable sort, những nhân viên cùng mức lương vẫn giữ thứ tự tên A-Z trong nhóm đó. Nếu dùng non-stable sort (Quick / Heap), thứ tự tên trong cùng nhóm lương sẽ bị xáo trộn tùy ý.

-- Ví dụ: nhân viên đã sort theo tên
-- [Alice:50k, Bob:50k, Charlie:60k, David:50k]

-- Sau stable sort theo lương:
-- [Alice:50k, Bob:50k, David:50k, Charlie:60k]
-- Alice, Bob, David vẫn theo thứ tự gốc (A-B-D) trong nhóm 50k

-- Sau non-stable sort theo lương:
-- [David:50k, Alice:50k, Bob:50k, Charlie:60k]  -- thứ tự trong nhóm 50k: không xác định

Time: O(n log n) Space: O(n)

Java standard library:

• Khi sort Object[] hoặc List — dùng TimSort (stable). Mọi element bằng nhau giữ original order.
• Khi sort mảng số nguyên nguyên thủy — dùng Dual-Pivot Quicksort (non-stable). Primitive không có "identity" — hai số nguyên có giá trị 5 là hoàn toàn equivalent, không cần distinguish thứ tự. Vì vậy stability không có ý nghĩa với primitive.

6. In-place vs O(n) extra space

"In-place" thường được định nghĩa là O(1) auxiliary space — không tính space cho input array và recursion stack.

Quick sort / Heap sort: in-place theo định nghĩa này. Quick sort dùng O(log n) recursion stack trung bình, nhưng không cần buffer phụ bằng kích thước n.

Merge sort: cần O(n) buffer cho merge step. Peak RAM khoảng 2x kích thước input. Với mảng 100MB, cần thêm 100MB buffer.

External sort (khi data vượt RAM) sẽ được cover ở Module 2 lesson 08 mini-challenge — adapt Merge sort để sort file 10GB với 1GB RAM bằng k-way merge.

7. Adaptive sort — TimSort khai thác partially-sorted data

"Adaptive" nghĩa là algorithm nhanh hơn khi input đã (gần) sorted.

Insertion sort là adaptive cơ bản nhất: với nearly-sorted array (mỗi element chỉ lệch vài vị trí khỏi vị trí đúng), Insertion sort chạy gần O(n). Với array đã sorted hoàn toàn, chính xác O(n).

TimSort — algorithm mặc định của Java cho Object array — khai thác điều này mạnh hơn nhiều:

1. Scan qua input, tìm các "run" — đoạn đã sorted hoặc reversed. Extend run ngắn bằng Insertion sort.
2. Merge các run lại theo thứ tự tối ưu (không merge tuần tự mà dùng stack-based strategy).

Kết quả: với timestamp log file hoặc array monotone ID (tất cả tăng dần), TimSort chạy gần O(n) thay vì O(n log n). Real-world data thường có pattern này — đây là lý do Python và Java đều dùng TimSort làm default cho Object array.

Cross-link: Module 2 lesson 09 sẽ là case study sâu về TimSort internals — galloping mode, run detection, merge policy.

8. Pitfall tổng hợp

Pitfall 1 — Big-O cùng n log n không có nghĩa là tốc độ bằng nhau

Quick sort (average) và Merge sort cùng O(n log n) average, nhưng Quick sort thường nhanh hơn 25-40% trên random integer array:

• Cache locality: Quick sort access memory theo thứ tự gần tuần tự trong partition step. Merge sort access hai half-array khác nhau → nhiều cache miss hơn.
• No allocation: Quick sort không cần buffer phụ → không tốn thời gian cấp phát.
• Constant factor: O notation ẩn constant. Quick sort có constant nhỏ hơn Merge sort trên random data.

Pitfall 2 — Nhầm stable và non-stable sort khi sort theo nhiều key

-- Bước 1: sort theo lương (stable)
-- [Alice:50k, Bob:50k, David:50k, Charlie:60k]

-- Bước 2: sort theo phòng ban bằng NON-STABLE sort
-- => thứ tự lương trong cùng phòng ban: không xác định (sai)

-- Bước 2 đúng: phải dùng stable sort
-- => trong cùng phòng ban, thứ tự lương từ bước 1 được bảo toàn

Time: O(n log n) Space: O(n)

Khi cần stable sort: dùng Merge sort hoặc TimSort. Khi sort primitive và không cần stable: Quick sort nhanh hơn.

Pitfall 3 — list.stream().sorted() không mutate list gốc

-- list.sort()           -- mutate list tại chỗ (in-place)
-- list.stream().sorted() -- tạo stream mới, list gốc KHÔNG thay đổi

Pattern nguy hiểm: tưởng stream().sorted() đã sort list gốc → đọc lại list gốc thấy thứ tự sai. Khi cần sort in-place, dùng list.sort(). Khi cần functional style không thay đổi original, dùng stream().sorted().collect().

9. Ứng dụng thực tế

Database ORDER BY: Postgres và MySQL phân tích query để chọn algorithm. Nếu data fit vào work_mem (Postgres, mặc định 4MB), dùng in-memory Quick sort. Nếu data vượt work_mem, chuyển sang external merge sort — chia thành các sorted run, ghi ra disk, merge lại. Module 2 lesson 08 mini-challenge sẽ implement external sort.

Apache Spark — distributed sort: với dataset hàng terabyte, Spark dùng sample sort — lấy sample từ data để ước lượng distribution, chia key space thành R range (R = số reducer), gửi mỗi key đến đúng reducer, mỗi reducer sort range của mình. Kết quả globally sorted mà không cần một node xử lý toàn bộ data.

Top-K query: không cần full sort, chỉ cần K phần tử lớn nhất. Heap size K cho O(n log k) thay vì O(n log n). Ví dụ: top 10 trending products từ 10 triệu transaction — sort toàn bộ là lãng phí. Module 2 lesson 05 (Heap sort) sẽ cover heap-based top-K.

Lucene segment merge: mỗi Lucene index segment là một sorted list of terms. Khi merge nhiều segment, Lucene dùng k-way merge — tương tự Merge sort nhưng merge k sorted list cùng lúc thay vì 2. Module 2 lesson 03 (Merge sort) và lesson 08 sẽ cover k-way merge pattern.

Redis ZSET (Sorted Set): dùng skip list để maintain sorted order tự động sau mỗi insert/update/delete — O(log n) per operation, không cần sort lại toàn bộ. Module 2 lesson 07 sẽ deep dive skip list structure và tại sao Redis chọn skip list thay vì balanced BST.

10. Deep Dive

11. Tóm tắt

• Comparison sort lower bound là Θ(n log n): mọi algorithm chỉ dùng so sánh không thể tốt hơn — chứng minh qua decision tree với n! leaf.
• Non-comparison sort (Counting, Radix) bypass bằng key range: không so sánh element, dùng index arithmetic → O(n+k) hoặc O(n×d) nhưng yêu cầu biết trước key range.
• Năm thuộc tính phân loại: comparison-based, stable, in-place, adaptive, online — không algorithm nào thắng cả 5.
• Java dùng algorithm khác cho primitive và Object: primitive không cần stable (không có identity) → Dual-Pivot Quicksort nhanh hơn. Object cần stable → TimSort.
• Quick sort nhanh hơn Merge sort khoảng 30% trên random data dù cùng O(n log n) average — cache locality và không cần buffer allocation.
• TimSort khai thác partially-sorted data: detect run, extend bằng Insertion sort, merge theo chiến lược tối ưu → gần O(n) cho real-world data.
• Stability quan trọng khi sort theo secondary key sau khi đã sort theo primary key — non-stable sort sẽ xáo trộn primary order trong ties.

12. Tự kiểm tra

Bài tiếp theo: Quadratic sorts — Insertion / Selection / Bubble