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

TL;DR: Quick sort nhanh hơn Merge sort 30-40% trên random data dù cùng O(n log n) average — nhờ cache locality (partition scan tuần tự), zero buffer allocation, và JIT-friendly inner loop. Cơ chế cốt lõi là partition: chọn pivot, sắp xếp lại sao cho mọi phần tử bên trái nhỏ hơn pivot và bên phải lớn hơn, pivot về đúng vị trí vĩnh viễn. Hoare partition nhanh hơn Lomuto khoảng 3x về số swap — mọi production library dùng Hoare. Worst case O(n²) khi pivot luôn chọn min/max; JDK tránh bằng Tukey ninther + Introsort fallback sang Heap sort. Non-stable — không dùng cho multi-key sort pipeline.

Trên mảng 1 triệu số nguyên ngẫu nhiên, built-in sort của Java chạy dưới 50ms — nhanh hơn Merge sort khoảng 30-40% dù cả hai cùng độ phức tạp O(n log n) trung bình. Điều đó có vẻ mâu thuẫn: cùng Big-O, sao kết quả đo được lại khác biệt lớn thế?

Câu trả lời nằm ở ba yếu tố mà Big-O không thể hiện: cache locality (Quick sort truy cập bộ nhớ tuần tự hơn), zero buffer allocation (không cần O(n) buffer phụ như Merge sort), và JIT-friendly inner loop (vòng lặp partition đơn giản, biên dịch ra assembly rất hiệu quả). Đổi lại, Quick sort có worst case O(n²) khi gặp adversarial input — và worst case đó hoàn toàn có thể bị khai thác cố ý.

Bài này dạy partition mechanics, pivot strategies, Dual-Pivot improvement của Vladimir Yaroslavskiy đang chạy trong JDK, và lý do Quick sort thắng cho primitive nhưng thua TimSort cho Object.

1. Analogy — Sắp bài bằng "chọn một quân làm mốc"

Hình dung bạn có 10 quân bài xáo trộn, cần sắp theo thứ tự.

Cách Quick sort: chọn một quân làm mốc (pivot). Chia phần còn lại thành hai nhóm: nhỏ hơn pivot thì sang trái, lớn hơn pivot thì sang phải. Pivot bây giờ ở đúng vị trí cuối cùng của nó — không bao giờ phải di chuyển lại. Lặp lại cho nhóm trái và nhóm phải.

2. Partition mechanics — Lomuto vs Hoare

Partition là bước cốt lõi của Quick sort: cho array A[lo..hi], chọn pivot và sắp xếp lại sao cho tất cả element nhỏ hơn pivot đứng trước pivot, tất cả lớn hơn đứng sau.

2.1 Lomuto partition (đơn giản, dễ hiểu)

LomutoPartition(A, lo, hi):
    pivot <- A[hi]              -- pivot là phần tử cuối
    i <- lo - 1                 -- i = ranh giới: mọi phần tử tại/trước i đều <= pivot
    for j <- lo đến hi-1:
        if A[j] <= pivot:
            i <- i + 1
            swap A[i] và A[j]
    -- đặt pivot vào vị trí đúng
    swap A[i+1] và A[hi]
    return i + 1                -- chỉ số của pivot

Time: O(n) Space: O(1)

Sau khi LomutoPartition trả về p: A[lo..p-1] đều nhỏ hơn hoặc bằng A[p], và A[p+1..hi] đều lớn hơn A[p]. Pivot A[p] ở vị trí đúng vĩnh viễn.

2.2 Hoare partition (hiệu quả hơn — JDK dùng variant này)

HoarePartition(A, lo, hi):
    pivot <- A[lo + (hi - lo) / 2]    -- phần tử giữa làm pivot
    i <- lo - 1
    j <- hi + 1
    while true:
        repeat i <- i + 1 until A[i] >= pivot    -- tiến i cho đến khi A[i] >= pivot
        repeat j <- j - 1 until A[j] <= pivot    -- lùi j cho đến khi A[j] <= pivot
        if i >= j: return j                       -- hai con trỏ gặp nhau -- xong
        swap A[i] và A[j]

Time: O(n) Space: O(1)

Hoare partition trả về chỉ số j — khác với Lomuto, A[j] không nhất thiết là pivot. Invariant: A[lo..j] đều nhỏ hơn hoặc bằng A[j+1..hi].

Vì sao Hoare nhanh hơn Lomuto?

Lomuto swap khoảng 3 lần nhiều hơn Hoare trên random data. Hoare dùng hai con trỏ hội tụ từ hai đầu — mỗi element chỉ bị scan một lần và swap tối thiểu. Mọi production sorting library đều dùng Hoare hoặc variant của nó.

3. Pseudocode đầy đủ — Quick sort với Hoare

QuickSort(A):
    QuickSort_helper(A, 0, A.length - 1)

QuickSort_helper(A, lo, hi):
    if lo < hi:
        p <- HoarePartition(A, lo, hi)
        QuickSort_helper(A, lo, p)        -- lưu ý: p, không phải p-1 (Hoare invariant)
        QuickSort_helper(A, p + 1, hi)

Time: O(n log n) average, O(n²) worst Space: O(log n) recursion stack

3.1 Trace ví dụ: [3, 1, 4, 1, 5, 9, 2, 6]

Ban đầu: [3, 1, 4, 1, 5, 9, 2, 6]  lo=0 hi=7
pivot = A[3] = 1

Hoare scan:
  i tiến phải: A[0]=3 >= 1, dừng tại i=0
  j lùi trái:  A[7]=6 > 1, A[6]=2 > 1, A[5]=9 > 1,
               A[4]=5 > 1, A[3]=1 = 1, dừng tại j=3
  i < j: swap A[0] và A[3] -> [1, 1, 4, 3, 5, 9, 2, 6]
  i tiến phải: A[1]=1 = 1, dừng tại i=1
  j lùi trái:  A[2]=4 > 1, A[1]=1 = 1, dừng tại j=1
  i >= j: return j=1

Đệ quy trái:  QuickSort([1, 1, ...], 0, 1)  -> đã sorted
Đệ quy phải: QuickSort([..., 4, 3, 5, 9, 2, 6], 2, 7)
  pivot = A[4] = 5
  ... (tiếp tục partition)

Kết quả cuối: [1, 1, 2, 3, 4, 5, 6, 9]

4. Pivot strategies — chọn quân nào làm mốc

Lựa chọn pivot quyết định chất lượng partition: pivot tốt chia array thành hai nửa gần bằng nhau → recursion tree cân bằng → O(n log n). Pivot xấu chia 1:n-1 mỗi lần → recursion depth n → O(n²).

4.1 First hoặc last element

pivot <- A[lo]   -- hoặc A[hi]

Đơn giản nhất. Nhưng với input đã sorted tăng dần (hoặc giảm dần), mỗi partition luôn tạo nhóm rỗng và nhóm n-1 phần tử → O(n²). Đây là worst case kinh điển.

4.2 Random pivot

mid <- lo + random(hi - lo + 1)   -- chỉ số ngẫu nhiên trong [lo, hi]
swap A[mid] và A[hi]
pivot <- A[hi]
-- rồi dùng Lomuto style với A[hi] làm pivot

Randomization đảm bảo expected O(n log n) bất kể thứ tự input. Adversarial input không thể biết trước pivot sẽ là gì → không thể craft worst case.

4.3 Median-of-three

mid <- lo + (hi - lo) / 2
-- sắp xếp A[lo], A[mid], A[hi] theo thứ tự tăng dần
if A[lo] > A[mid]: swap A[lo] và A[mid]
if A[lo] > A[hi]:  swap A[lo] và A[hi]
if A[mid] > A[hi]: swap A[mid] và A[hi]
pivot <- A[mid]    -- median của 3 phần tử

Lấy median của A[lo], A[mid], A[hi] làm pivot. Tốt hơn first/last element đáng kể — sorted input không còn là worst case nữa. Không cần random number generator.

4.4 Tukey ninther (JDK choice)

Với array lớn (vượt ngưỡng), JDK dùng Tukey ninther: lấy 9 mẫu từ array, chia thành 3 nhóm 3 phần tử, lấy median của mỗi nhóm, rồi lấy median của 3 median đó. Kết quả: pivot đại diện tốt cho distribution thực tế, gần như không bao giờ rơi vào worst case với data thực.

-- Tukey ninther (rút gọn):
-- chia array thành 9 vị trí đều nhau: a0, a1, ..., a8
-- median(a0,a1,a2) -> m0
-- median(a3,a4,a5) -> m1
-- median(a6,a7,a8) -> m2
-- pivot <- median(m0, m1, m2)

Thử ngẫmTukey ninther lấy median-của-3-median từ 9 mẫu để pivot gần như không rơi vào worst case với data thực. Với một mảng đã sort ngược hoàn toàn, pivot "first element" ở 4.1 rơi vào trường hợp nào?

5. Worst case O(n²) và adversarial input

Khi pivot luôn là element nhỏ nhất (hoặc lớn nhất), partition chia [0, n-1] thay vì [n/2, n/2]:

Kích thước partition: n, n-1, n-2, ..., 1
Số phép so sánh:      n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)

Input kill first-element pivot:

• Sorted tăng dần: [1, 2, 3, 4, 5] → pivot = 1 mỗi lần, chia 0:n-1.
• Sorted giảm dần: [5, 4, 3, 2, 1] → pivot = 5 mỗi lần, chia n-1:0.

Real attack — DoS production sort:

Nếu attacker biết pivot strategy (ví dụ: luôn chọn first element), họ có thể craft input để force O(n²) → server mất hàng phút sort thay vì milliseconds. McIlroy 1999 ("Quicksort Killer Adversaries") mô tả cách generate adversarial input cho bất kỳ pivot strategy nào.

Defense trong JDK: Dual-Pivot Quicksort dùng Tukey ninther và thêm logic detect degenerate case (khi nhiều partition liên tiếp không cân bằng, switch sang Heap sort — đây là Introsort pattern). Adversary thông thường không thể biết trước 9 sample points.

flowchart TD
    START["QuickSort(A, lo, hi)"]
    CHECK_SIZE{"hi - lo < THRESHOLD?"}
    INSERT["Insertion sort<br/>(n nhỏ, constants thắng)"]
    CHECK_DEPTH{"recursion depth<br/>vượt ngưỡng?"}
    HEAP["Heap sort<br/>(O(n log n) guaranteed)"]
    PIVOT["Chọn pivot<br/>Tukey ninther"]
    PARTITION["Dual-Pivot Partition<br/>3 vùng"]
    RECURSE["Đệ quy trái, giữa, phải"]

    START --> CHECK_SIZE
    CHECK_SIZE -- "có" --> INSERT
    CHECK_SIZE -- "không" --> CHECK_DEPTH
    CHECK_DEPTH -- "có (degenerate)" --> HEAP
    CHECK_DEPTH -- "không" --> PIVOT
    PIVOT --> PARTITION
    PARTITION --> RECURSE
    RECURSE --> START

6. Dual-Pivot Quicksort (Java 7+)

Vladimir Yaroslavskiy đề xuất năm 2009: thay vì 1 pivot, dùng 2 pivot p1 ≤ p2 và chia array thành 3 vùng:

[ phần tử < p1 | p1 <= x <= p2 | phần tử > p2 ]
     vùng trái      vùng giữa       vùng phải

DualPivotPartition(A, lo, hi):
    -- đảm bảo A[lo] <= A[hi]
    if A[lo] > A[hi]: swap A[lo] và A[hi]
    p1 <- A[lo]; p2 <- A[hi]

    lt <- lo + 1    -- ranh giới: A[lo+1..lt-1] < p1
    gt <- hi - 1    -- ranh giới: A[gt+1..hi-1] > p2
    k  <- lo + 1    -- con trỏ scan hiện tại

    while k <= gt:
        if A[k] < p1:
            swap A[k] và A[lt]; lt <- lt + 1; k <- k + 1
        else if A[k] > p2:
            swap A[k] và A[gt]; gt <- gt - 1
            -- k không tăng vì A[gt] mới chưa được kiểm tra
        else:
            k <- k + 1

    -- đặt pivot vào đúng vị trí
    lt <- lt - 1; gt <- gt + 1
    swap A[lo] và A[lt]
    swap A[hi] và A[gt]

    -- đệ quy 3 vùng
    DualPivotSort(A, lo, lt - 1)
    DualPivotSort(A, lt + 1, gt - 1)
    DualPivotSort(A, gt + 1, hi)

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

Vì sao nhanh hơn?

Với 1 pivot, mỗi partition call tạo 2 sub-problem mỗi cái kích thước khoảng n/2. Với 2 pivot, tạo 3 sub-problem mỗi cái kích thước khoảng n/3. Recursion tree thấp hơn → tổng số swap ít hơn.

Ngoài ra, 3-way partition xử lý duplicate-heavy input tốt hơn: với nhiều phần tử bằng nhau, vùng giữa nhanh chóng trở nên lớn và không cần recurse thêm.

Yaroslavskiy 2009 đo được khoảng 30% ít swap hơn trên random integer data so với classic single-pivot. OpenJDK đưa vào Java 7 sau khi benchmark xác nhận.

Thử ngẫm3-way partition với 2 pivot tạo 3 sub-problem kích thước n/3 thay vì n/2. Với một mảng toàn phần tử giống hệt nhau, vùng giữa lớn cỡ nào và điều đó rút ngắn gì?

7. Quick sort properties

8. Pitfall tổng hợp

Pitfall 1 — Stack overflow trên adversarial input

-- Naive: luôn chọn phần tử đầu làm pivot
QuickSort_NAIVE(A, lo, hi):
    if lo >= hi: return
    pivot <- A[lo]   -- BUG: O(n²) và O(n) stack với sorted input
    -- ...partition...
    QuickSort_NAIVE(A, lo, p - 1)
    QuickSort_NAIVE(A, p + 1, hi)

-- Test: QuickSort_NAIVE([1,2,3,...,100000], 0, 99999)
-- -> stack overflow: recursion depth 100.000

Fix: dùng median-of-three pivot, random pivot, hoặc tail-recurse trên nửa nhỏ hơn và iterate trên nửa lớn hơn (giảm stack depth tối đa xuống O(log n) ngay cả khi partition không cân bằng).

Pitfall 2 — Quick sort không stable: sort tuple theo 2 key sẽ break

-- Bài toán: sort employees theo salary, rồi theo name
-- Mục tiêu: trong cùng name, giữ thứ tự salary từ bước 1

-- Bước 1: sort theo salary (stable sort)
-- [Alice:50k, Alice:30k, Bob:20k] -> [Bob:20k, Alice:30k, Alice:50k]

-- Bước 2: sort theo name bằng NON-STABLE Quick sort
-- -> Alice:50k có thể đứng trước Alice:30k -> SAI
-- -> thứ tự salary trong cùng name: không xác định

-- ĐÚNG: dùng stable sort ở bước 2 (Merge sort, TimSort)
-- -> trong cùng name, thứ tự salary từ bước 1 được bảo toàn

Pitfall 3 — Quên switch sang Insertion sort cho subarray nhỏ

-- CHẬM: đệ quy xuống đến kích thước 1
QuickSort_SLOW(A, lo, hi):
    if lo >= hi: return      -- base case: kích thước 0 hoặc 1
    -- Với kích thước 2-10, overhead Quick sort (function call, partition setup)
    -- vượt quá lợi ích so với Insertion sort đơn giản
    p <- HoarePartition(A, lo, hi)
    QuickSort_SLOW(A, lo, p)
    QuickSort_SLOW(A, p + 1, hi)

-- NHANH: switch sang Insertion sort khi subarray nhỏ
THRESHOLD <- 47   -- cùng giá trị JDK DualPivotQuicksort

QuickSort_FAST(A, lo, hi):
    if hi - lo < THRESHOLD:
        InsertionSort(A, lo, hi)   -- Insertion sort thắng với n nhỏ
        return
    p <- HoarePartition(A, lo, hi)
    QuickSort_FAST(A, lo, p)
    QuickSort_FAST(A, p + 1, hi)

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

JDK dùng threshold 47. Với subarray nhỏ hơn 47, Insertion sort nhanh hơn Quick sort vì overhead function call + partition setup vượt quá lợi ích của O(n log n). Cross-link: Module 2 lesson 02 giải thích vì sao Insertion sort adaptive và fast cho small n.

Thử ngẫmTHRESHOLD = 47 nghĩa là dưới ngưỡng đó, overhead function call ăn hết lợi thế O(n log n). Đổi THRESHOLD lên 200, phần hiệu năng nào cải thiện và phần nào tệ đi?

9. Java standard library

-- Arrays.sort(primitive[]) -- Dual-Pivot Quicksort (Yaroslavskiy 2009, Java 7+)
-- Best: O(n), Average: O(n log n), Worst: O(n²) (hiếm với Tukey ninther)
-- Non-stable. Switch sang Insertion sort dưới threshold 47.

-- Arrays.sort(Object[]) -- TimSort (Python 2002, Java 7)
-- Best: O(n), Average: O(n log n), Worst: O(n log n) guaranteed
-- Stable. Dùng merge buffer O(n).

-- Collections.sort(List) -- ủy quyền cho List.sort() -- TimSort
-- Stream.sorted() -- buffer tất cả phần tử, áp dụng TimSort, emit

-- Arrays.parallelSort(primitive[]) -- fork-join + Dual-Pivot
-- Threshold: 8192 phần tử; dưới threshold dùng sequential sort

Tóm tắt decision:

• Primitive array → Dual-Pivot Quicksort (fast, non-stable — stability không có nghĩa với primitive).
• Object array hoặc List → TimSort (stable, O(n log n) guaranteed).
• parallelSort() → Parallel Dual-Pivot với fork-join, chỉ có lợi trên array vượt 8192 phần tử.

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

Lucene sort: Lucene cần sort các term byte[] khi flush segment ra disk. Đây là primitive-like data không cần stable → Quick sort variant được dùng để tối đa tốc độ.

Database ORDER BY in-memory: PostgreSQL tuple sort (khi data fit vào work_mem) dùng Quick sort với Insertion sort fallback cho sub-run nhỏ. Khi data vượt work_mem, chuyển sang external merge sort (Module 2 lesson 08).

GPU sorting libraries: các thư viện CUDA sort cho GPU dùng Quick sort variants vì partition step dễ song song hóa hơn Merge sort — hai half có thể sort hoàn toàn độc lập trên different thread blocks.

C qsort(): POSIX standard library function, Quick sort variant. Thường chậm hơn Java built-in sort vì dùng function pointer comparator — mỗi so sánh là một indirect call qua pointer, JIT không thể inline. Java Comparator được JIT inline trong warm code path.

11. Deep Dive

12. Tóm tắt

• Quick sort thắng về tốc độ thực tế so với Merge sort dù cùng O(n log n) average — cache locality, zero buffer allocation, và JIT-friendly inner loop tạo ra hằng số nhỏ hơn.
• Hoare partition hiệu quả hơn Lomuto khoảng 3x về swap count — mọi production library đều dùng Hoare hoặc variant của nó.
• Pivot strategy quyết định worst case: first/last element → O(n²) trên sorted input. Random pivot hoặc median-of-three → kháng adversarial input thông thường.
• Dual-Pivot Quicksort (Java 7+): 2 pivot tạo 3 vùng, empirically nhanh hơn single-pivot khoảng 30% trên random data — algorithm của Yaroslavskiy 2009 đang chạy trong built-in sort primitive.
• Worst case O(n²) và adversarial input: pivot strategy cố định có thể bị khai thác cố ý. JDK defense: Tukey ninther + Introsort fallback sang Heap sort khi detect degenerate partitioning.
• Non-stable: Quick sort không phù hợp cho multi-key sort pipeline. Dùng sort object (TimSort, stable) khi cần stability.
• Switch sang Insertion sort dưới threshold 47: optimization quan trọng mà custom implementation thường bỏ qua.

13. Tự kiểm tra

Bài tiếp theo: Heap sort — binary heap, build-heap O(n), và top-K pattern