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

Trên mảng int[] 1 triệu phần tử ngẫu nhiên, Arrays.sort(int[]) 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, JIT compile 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 int[] 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 arr[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)

private static int lomutoPartition(int[] arr, int lo, int hi) {
    int pivot = arr[hi];  // pivot is last element
    int i = lo - 1;       // i = boundary: everything at/before i is <= pivot
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    // place pivot at its final position
    int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;
    return i + 1;  // pivot index
}

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

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

private static int hoarePartition(int[] arr, int lo, int hi) {
    int pivot = arr[lo + (hi - lo) / 2];  // middle element as pivot
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);   // advance i until arr[i] >= pivot
        do { j--; } while (arr[j] > pivot);   // retreat j until arr[j] <= pivot
        if (i >= j) return j;                  // pointers met -- partition done
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

Hoare partition trả về chỉ số j — khác với Lomuto, arr[j] không nhất thiết là pivot. Invariant: arr[lo..j] đều nhỏ hơn hoặc bằng arr[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. Code Java đầy đủ — Quick sort với Hoare

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int lo, int hi) {
    if (lo < hi) {
        int p = hoarePartition(arr, lo, hi);
        quickSort(arr, lo, p);       // note: p, not p-1 (Hoare invariant)
        quickSort(arr, p + 1, hi);
    }
}

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

Initial: [3, 1, 4, 1, 5, 9, 2, 6]  lo=0 hi=7
pivot = arr[3] = 1

Hoare scan:
  i moves right: arr[0]=3 >= 1, stops at i=0
  j moves left:  arr[7]=6 > 1, arr[6]=2 > 1, arr[5]=9 > 1,
                 arr[4]=5 > 1, arr[3]=1 = 1, stops at j=3
  i < j: swap arr[0] and arr[3] -> [1, 1, 4, 3, 5, 9, 2, 6]
  i moves right: arr[1]=1 = 1, stops at i=1
  j moves left:  arr[2]=4 > 1, arr[1]=1 = 1, stops at j=1
  i >= j: return j=1

Recurse left:  quickSort([1, 1, ...], 0, 1)  -> already sorted
Recurse right: quickSort([..., 4, 3, 5, 9, 2, 6], 2, 7)
  pivot = arr[4] = 5
  ... (further partitions)

Sau đủ recursion, array sorted: [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

int pivot = arr[lo];   // hoặc arr[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

int mid = lo + random.nextInt(hi - lo + 1);
int tmp = arr[mid]; arr[mid] = arr[hi]; arr[hi] = tmp;
// then use arr[hi] as pivot (Lomuto style)

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. Trade-off: random.nextInt() có overhead nhỏ per call.

4.3 Median-of-three

int mid = lo + (hi - lo) / 2;
// sort lo, mid, hi and use arr[mid] as pivot
if (arr[lo] > arr[mid]) { swap(arr, lo, mid); }
if (arr[lo] > arr[hi])  { swap(arr, lo, hi); }
if (arr[mid] > arr[hi]) { swap(arr, mid, hi); }
int pivot = arr[mid];

Lấy median của arr[lo], arr[mid], arr[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 Median-of-medians (Blum-Floyd-Pratt-Rivest-Tarjan, 1973)

Thuật toán lý thuyết chọn pivot đảm bảo partition luôn ít nhất 30-70 split → O(n log n) worst case guaranteed. Nhưng constant factor lớn (khoảng 10x) so với random pivot → không dùng trong production.

4.5 JDK choice — Tukey ninther

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.

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]:

Partition size: n, n-1, n-2, ..., 1
Comparisons:    n + (n-1) + ... + 1 = n(n+1)/2 = O(n²)

Input kill first-element pivot:

• Sorted ascending: [1, 2, 3, 4, 5] → pivot = 1 mỗi lần, chia 0:n-1.
• Sorted descending: [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 spend hàng phút sort thay vì milliseconds. Đây là vector tấn công thực tế, không chỉ lý thuyết. 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.

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:

[ < p1 | p1 <= x <= p2 | > p2 ]
   left      middle       right

// Simplified dual-pivot partition (illustrative -- not exact JDK code)
private static void dualPivotSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;

    // ensure arr[lo] <= arr[hi]
    if (arr[lo] > arr[hi]) {
        int tmp = arr[lo]; arr[lo] = arr[hi]; arr[hi] = tmp;
    }
    int p1 = arr[lo], p2 = arr[hi];

    int lt = lo + 1;  // boundary: arr[lo+1..lt-1] < p1
    int gt = hi - 1;  // boundary: arr[gt+1..hi-1] > p2
    int k  = lo + 1;  // current scan pointer

    while (k <= gt) {
        if (arr[k] < p1) {
            int tmp = arr[k]; arr[k] = arr[lt]; arr[lt] = tmp;
            lt++; k++;
        } else if (arr[k] > p2) {
            int tmp = arr[k]; arr[k] = arr[gt]; arr[gt] = tmp;
            gt--;
        } else {
            k++;
        }
    }
    // place pivots
    lt--; gt++;
    int tmp = arr[lo]; arr[lo] = arr[lt]; arr[lt] = tmp;
    tmp = arr[hi]; arr[hi] = arr[gt]; arr[gt] = tmp;

    dualPivotSort(arr, lo, lt - 1);
    dualPivotSort(arr, lt + 1, gt - 1);
    dualPivotSort(arr, gt + 1, hi);
}

Vì sao nhanh hơn?

Với 1 pivot, mỗi partition call thực hiện n so sánh và tạo 2 sub-problem. Với 2 pivot, mỗi partition call vẫn thực hiện khoảng n so sánh nhưng tạo 3 sub-problem — mỗi sub-problem nhỏ hơn khoảng n/3 thay vì n/2. Recursion tree thấp hơn → tổng số swap ít hơn.

Empirically: Dual-Pivot Quick nhanh hơn classic single-pivot khoảng 30% trên random integer data (Yaroslavskiy 2009 benchmarks). OpenJDK đưa vào Java 7 sau khi benchmark xác nhận.

OpenJDK DualPivotQuicksort.java (Java 21, trích đoạn logic chính):

// From OpenJDK DualPivotQuicksort.java (simplified for illustration)
// Sort using dual-pivot quicksort when array is large enough
if (last - from > QUICKSORT_THRESHOLD) {
    // Pick two pivots from five equally spaced positions
    int fifth = (last - from) / 5;
    // ... (Tukey ninther logic for pivot selection)
    // three-way partition around p1, p2
}
// Fall back to insertion sort for small subarrays
if (last - from < INSERTION_SORT_THRESHOLD) {
    insertionSort(arr, from, to, low, high);
}

7. Quick sort properties

8. Pitfall tổng hợp

Pitfall 1 — Stack overflow trên adversarial input

// Naive: always pick first element as pivot
private static void naiveQuickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = arr[lo];  // BAD: O(n^2) and O(n) stack on sorted input
    // ...partition...
    naiveQuickSort(arr, lo, p - 1);
    naiveQuickSort(arr, p + 1, hi);
}

// Test: naiveQuickSort(new int[100_000], 0, 99_999)
// -> StackOverflowError: 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

// Employee: {name, salary}. Sort by salary stable, then by name stable.
// If using non-stable sort for second pass, first-pass order is destroyed.

Employee[] employees = { ... };

// Step 1: sort by salary
Arrays.sort(employees, Comparator.comparingInt(Employee::getSalary));
// Step 2: sort by name -- MUST be stable to preserve salary order within same name
Arrays.sort(employees, Comparator.comparing(Employee::getName));
// Arrays.sort(Object[]) uses TimSort -- stable. OK.

// WRONG: using a naive QuickSort for step 2 would break salary order within same name

Dùng Arrays.sort(Integer[]) hoặc Collections.sort() (TimSort, stable) khi cần stable sort. KHÔNG nhầm sang Arrays.sort(int[]) (Dual-Pivot Quick, non-stable) khi sort objects theo multi-key.

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

// SLOW: recurse all the way down to size 1
private static void slowQuickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;  // base case: size 0 or 1
    // For size 2-10, quicksort overhead (function call, partition setup)
    // exceeds benefit compared to simple insertion sort
    int p = hoarePartition(arr, lo, hi);
    slowQuickSort(arr, lo, p);
    slowQuickSort(arr, p + 1, hi);
}

// FAST: switch to insertion sort for small subarrays
private static final int THRESHOLD = 47; // same as JDK DualPivotQuicksort

private static void fastQuickSort(int[] arr, int lo, int hi) {
    if (hi - lo < THRESHOLD) {
        insertionSort(arr, lo, hi);  // insertion sort wins for small n
        return;
    }
    int p = hoarePartition(arr, lo, hi);
    fastQuickSort(arr, lo, p);
    fastQuickSort(arr, p + 1, hi);
}

JDK dùng threshold 47 (xem INSERTION_SORT_THRESHOLD trong DualPivotQuicksort.java). 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 4 lesson 02 giải thích vì sao Insertion sort adaptive và fast cho small n.

9. Java standard library

// Arrays.sort(int[]) -- Dual-Pivot Quicksort (Yaroslavskiy 2009, Java 7+)
// Best: O(n), Average: O(n log n), Worst: O(n^2) (rare with Tukey ninther)
// Non-stable. Switches to Insertion sort under threshold 47.
int[] primitives = {5, 2, 8, 1, 9};
Arrays.sort(primitives);               // Dual-Pivot Quick

// Arrays.sort(long[]), double[], char[], short[], byte[] -- same Dual-Pivot
long[] longs = {100L, 50L, 200L};
Arrays.sort(longs);                    // Dual-Pivot Quick

// Arrays.sort(Object[]) -- TimSort (NOT Quick -- needs stable)
Integer[] boxed = {5, 2, 8, 1, 9};
Arrays.sort(boxed);                    // TimSort, stable

// Collections.sort(List<T>) -- delegates to TimSort
List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8));
Collections.sort(list);               // TimSort, stable

// Arrays.parallelSort(int[]) -- fork-join + Dual-Pivot
// Threshold: 8192 elements; below threshold falls back to sequential Arrays.sort
int[] large = new int[1_000_000];
Arrays.parallelSort(large);           // parallel Dual-Pivot, uses ForkJoinPool

Tóm tắt decision:

• Primitive array (int[], long[], double[], ...) → Dual-Pivot Quicksort (fast, non-stable — stability irrelevant for primitives).
• Object array (Integer[], String[], custom objects) → TimSort (stable, O(n log n) guaranteed).
• Collections.sort() → TimSort (stable).
• Arrays.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 BytesRefArray.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 4 lesson 08).

GPU sorting libraries (Thrust, CUB): 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 Arrays.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 hiện đang chạy trong Arrays.sort(int[]).
• 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 Arrays.sort(Integer[]) hoặc Collections.sort() (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.
• Arrays.sort(int[]) → Dual-Pivot Quick; Arrays.sort(Object[]) → TimSort: hai algorithm khác nhau cho hai loại khác nhau.

13. Tự kiểm tra

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