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

Bubble sort là ví dụ đầu tiên về sorting algorithm trong hầu hết giáo trình đại học — và cũng là thứ đầu tiên bị gạch chân đỏ trong code review. O(n²), chậm, không có lý do dùng trong production. Câu chuyện kết thúc ở đó.

Nhưng mở file DualPivotQuicksort.java trong OpenJDK, bạn thấy dòng:

// Use insertion sort for small arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) { ... }

INSERTION_SORT_THRESHOLD hiện tại là 47. Với subarray dưới 47 phần tử, JDK bỏ qua Dual-Pivot Quicksort và gọi thẳng Insertion sort. Python's TimSort và C++ IntroSort làm tương tự. Vì sao một algorithm O(n²) lại xuất hiện trong production library của ngôn ngữ lập trình chính?

Bài này so sánh 3 quadratic sort, code Java đầy đủ, đo benchmark, và lý giải vì sao Insertion sort là adaptive và vẫn xuất hiện trong production library.

1. Analogy — Ba cách sắp bài tay

Hình dung bạn có 10 quân bài xáo trộn, cần sắp theo thứ tự. Ba người bạn mỗi người dùng cách khác nhau:

Bubble — so từng cặp kế nhau, đổi chỗ nếu sai: Quét từ trái qua phải, so quân thứ i và i+1. Nếu sai thứ tự thì đổi. Sau một lượt, quân lớn nhất "nổi" lên cuối — như bong bóng nổi lên mặt nước. Quét lại, lần này bỏ qua vị trí cuối đã xong. Lặp cho đến khi không còn đổi nào.

Selection — tìm nhỏ nhất, đặt vào đầu: Lướt qua toàn bộ bài, chọn ra quân nhỏ nhất, đổi với quân ở vị trí đầu. Bây giờ vị trí đầu đã xong. Lặp lại với phần còn lại, mỗi lần chọn nhỏ nhất trong phần chưa xử lý.

Insertion — cầm từng quân, đẩy vào chỗ đúng: Cầm quân thứ 2, đẩy vào vị trí đúng trong 2 quân đầu. Cầm quân thứ 3, đẩy vào chỗ đúng trong 3 quân đầu. Phần bên trái tay luôn đã sorted — giống khi bạn cầm bài và xếp từng lá vào đúng vị trí.

2. Bubble sort

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;  // already sorted -- early exit
    }
}

Dòng if (!swapped) break là optimization quan trọng: nếu một pass không có swap nào, array đã sorted và thuật toán dừng sớm.

Phân tích:

• Best case O(n): input đã sorted → pass đầu không swap → break ngay. Một lần quét duy nhất.
• Worst case O(n²): input sorted ngược → mỗi element phải bubble qua toàn bộ array.
• Stable: yes. Điều kiện arr[j] > arr[j+1] — khi bằng nhau (==) không swap, giữ thứ tự gốc.
• In-place: yes. O(1) extra space.
• Adaptive: có early exit, nhưng thực tế vẫn chậm hơn Insertion sort trên nearly-sorted data.

Production rating: hiếm có lý do dùng. Nếu bạn thấy Bubble sort trong code review, replace ngay bằng Arrays.sort() hoặc Collections.sort().

3. Selection sort

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        // swap arr[i] with arr[minIdx]
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

Phân tích:

• Always O(n²): không adaptive. Dù input đã sorted hay sorted ngược, vòng lặp trong vẫn quét toàn bộ phần còn lại để tìm min. Không có early exit.
• Stable: no. Swap arr[i] với arr[minIdx] có thể nhảy qua element bằng nhau nằm giữa — phá vỡ thứ tự tương đối. Ví dụ: [3a, 3b, 1] → swap 3a với 1 → [1, 3b, 3a] — 3a và 3b đảo thứ tự.
• Ưu điểm duy nhất — ít swap: đúng n-1 lần swap, không bao giờ nhiều hơn. So với Bubble sort có thể swap tới n²/2 lần. Khi swap đắt (object lớn, disk write, hardware register), Selection sort có lợi thế.

Production rating: dùng khi swap đắt hơn compare. Hiếm trong Java vì Java array chứa reference (swap luôn O(1)). Phù hợp hơn với một số ngữ cảnh embedded hoặc sorting danh sách có large payload.

4. Insertion sort — adaptive winner

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {  // NOTE: j >= 0 MUST be first
            arr[j + 1] = arr[j];           // shift right, not swap
            j--;
        }
        arr[j + 1] = key;
    }
}

Cơ chế quan trọng: Insertion sort shift element sang phải thay vì swap từng cặp. Mỗi iteration chỉ ghi một lần vào arr[j+1] = key ở cuối — tiết kiệm hơn Bubble sort swap từng cặp.

Phân tích:

• Best case O(n): input đã sorted → while loop không bao giờ enter (điều kiện arr[j] > key false ngay) → chỉ có vòng for ngoài O(n).
• Worst case O(n²): input sorted ngược → mỗi key phải shift qua toàn bộ phần đã sorted.
• Adaptive — O(n + d): với d = số inversion (cặp (i,j) mà i < j nhưng arr[i] > arr[j]). Nearly-sorted array có d nhỏ → gần O(n). Đây là lợi thế chính.
• Stable: yes. Điều kiện arr[j] > key (strict greater) — khi bằng nhau không shift, giữ thứ tự gốc.
• Online: yes. Có thể sort data đến từng phần — nhận element mới, chèn vào vị trí đúng trong phần đã sorted.
• In-place: yes. O(1) extra space.

5. Bảng so sánh và benchmark thực tế

Ghi chú: "n" và "n²" trong bảng là ký hiệu rút gọn cho O(n) và O(n²).

Benchmark thực tế trên int[] 10,000 phần tử ngẫu nhiên (Java 21, JMH warm-up 5 iteration):

Insertion thắng Bubble và Selection khoảng 2x nhờ shift thay vì swap. Nhưng Arrays.sort nhanh hơn 50-100x — vì sao không dùng Arrays.sort cho mọi trường hợp?

Benchmark với n = 16 phần tử (subarray nhỏ):

Với n nhỏ, Arrays.sort chậm hơn Insertion sort vì overhead của recursion, pivot selection, và function call. Insertion sort chạy thẳng, không recursion, không allocation — thắng hoàn toàn ở n nhỏ.

Đây là lý do TimSort gọi Insertion sort cho subarray dưới 32 phần tử. Constants matter ở n nhỏ.

6. Pitfall tổng hợp

Pitfall 1 — Bubble sort trong code production

Bubble sort vẫn xuất hiện trong code production vì developer nhớ cú pháp từ năm nhất rồi copy paste. Kết quả: array 10,000 phần tử mất 120ms thay vì 1.2ms — chênh lệch 100x.

// WRONG: O(n^2) -- do not use in production
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) { /* swap */ }
    }
}

// CORRECT: O(n log n) -- one line, handles all edge cases
Arrays.sort(arr);

// For List<T>:
Collections.sort(list);  // or list.sort(Comparator.naturalOrder())

Rule: nếu bạn thấy Bubble sort trong code review, yêu cầu replace ngay. Không có use case production nào biện minh cho Bubble sort khi Arrays.sort / Collections.sort đã sẵn có.

Pitfall 2 — Selection sort không stable, nhưng dev assume mọi sort là stable

Selection sort không stable — swap arr[i] với arr[minIdx] có thể nhảy qua element bằng nhau. Nếu bạn sort employees theo salary, rồi theo department (giả định department sort giữ thứ tự salary trong cùng department), dùng Selection sort sẽ phá vỡ invariant này.

// Two-key sort: sort by salary first, then by department
// Expected: within same department, preserve salary order
employees.sort(Comparator.comparingInt(Employee::getSalary)); // stable (TimSort)
employees.sort(Comparator.comparing(Employee::getDepartment)); // stable (TimSort)
// => within same department, salary order preserved ✓

// If second sort were non-stable (Selection sort equivalent):
// salary order within same department: undefined ✗

Rule: trước khi dùng bất kỳ sort nào trong multi-key scenario, verify stability. Với Java standard library, Arrays.sort(Object[]) và Collections.sort() đều stable (TimSort). Arrays.sort(int[]) non-stable nhưng không có ý nghĩa với primitive.

Pitfall 3 — Thứ tự điều kiện trong Insertion sort while loop

// WRONG: ArrayIndexOutOfBoundsException khi j = -1
while (arr[j] > key && j >= 0) {
    // arr[j] evaluated when j = -1 -> index -1 -> exception
}

// CORRECT: short-circuit -- j >= 0 checked first
while (j >= 0 && arr[j] > key) {
    arr[j + 1] = arr[j];
    j--;
}

Java && short-circuit: khi j >= 0 là false, arr[j] > key không được evaluate. Đảo ngược thứ tự thì arr[j] được evaluate trước — với j = -1 gây ArrayIndexOutOfBoundsException. Lỗi này hay xuất hiện trong coding interview và code được viết "từ trí nhớ" mà không chạy test.

7. Insertion sort variants

Binary Insertion sort: thay vì tìm vị trí chèn bằng linear scan O(n), dùng binary search O(log n). Tổng số phép compare giảm xuống O(n log n). Nhưng tổng thời gian vẫn O(n²) vì shift phần tử vẫn tốn O(n) per iteration — shift dominates, không phải compare.

Variant này hữu ích cho linked list nơi insert O(1) (chỉ điều chỉnh pointer) — binary search + O(1) insert = O(n log n) thực sự. Với array, shift là bottleneck nên lợi ích hạn chế.

Shell sort: Insertion sort + gap sequence. Sort các phần tử cách nhau gap bước, sau đó giảm gap dần đến 1. Gap lớn đầu tiên đưa các phần tử về gần vị trí đúng, Insertion sort cuối cùng (gap = 1) chỉ cần điều chỉnh nhỏ. Worst case O(n^1.5) đến O(n log² n) tùy gap sequence — tốt hơn O(n²) thuần túy. Hiếm dùng trong production hiện đại nhưng có giá trị học thuật.

8. Vì sao TimSort vẫn dùng Insertion sort

Real-world data thường có structure — không random hoàn toàn. Log file sorted theo timestamp, transaction ID tăng dần, event stream có thứ tự tự nhiên. TimSort khai thác điều này qua 3 bước:

1. Detect run: quét input, tìm các đoạn đã sorted tăng dần hoặc giảm dần. Đoạn giảm thì reverse tại chỗ O(n).
2. Extend bằng Insertion sort: nếu run ngắn hơn minRunLength (32-64 phần tử), extend bằng Insertion sort đến đủ độ dài. Insertion sort cho subarray nhỏ gần O(n) vì subarray ngắn → ít inversion.
3. Merge các run: dùng stack-based merge strategy đảm bảo merge theo thứ tự tối ưu.

Insertion sort phù hợp ở bước 2 vì:

• Run ngắn (32-64 phần tử) → n nhỏ → Insertion sort thắng về constant factor.
• Run thường "gần sorted" → d (số inversion) nhỏ → Insertion sort gần O(n).
• Không cần recursion hay allocation → overhead thấp nhất có thể.

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

9. Applied to tech

Java DualPivotQuicksort.java — threshold 47: Arrays.sort(int[]) dùng Dual-Pivot Quicksort từ Java 7. Nhưng khi subarray dưới INSERTION_SORT_THRESHOLD (47 phần tử), switch sang Insertion sort:

// From OpenJDK DualPivotQuicksort.java (simplified)
private static void sort(int[] a, int left, int right, ...) {
    if (right - left < INSERTION_SORT_THRESHOLD) {
        // Use insertion sort on tiny arrays
        for (int i = left, j = i; i < right; j = ++i) {
            int ai = a[i + 1];
            while (ai < a[j]) {
                a[j + 1] = a[j];
                if (j-- == left) break;
            }
            a[j + 1] = ai;
        }
        return;
    }
    // ... dual-pivot partition and recurse
}

Threshold 47 được tìm ra qua benchmarking thực nghiệm — không phải con số lý thuyết.

Online algorithms — sort data streaming: Insertion sort có thể sort data khi nó đến từng phần — nhận event mới, chèn vào vị trí đúng trong phần đã sorted. Bubble sort và Selection sort cần full data trước khi bắt đầu.

Use case thực tế: buffer incoming trade orders và maintain sorted order by price/time priority. Với số lượng orders trong buffer thấp (thường dưới 100), Insertion sort O(n) cho insert vào sorted array thắng về latency so với rebuild + full sort.

Embedded / memory-constrained: Insertion sort code rất ngắn (~10 dòng), không dùng recursion stack, in-place O(1). Phù hợp microcontroller hoặc kernel-level sort nơi binary size và stack depth bị giới hạn nghiêm ngặt. Linux kernel dùng Insertion sort cho một số small list sort.

Educational tool — visualizing sorting: Bubble sort dễ visualize nhất vì swap kế nhau, mỗi bước thay đổi nhỏ và rõ ràng. Hầu hết sorting visualizer (sorting.at, visualgo.net) dùng Bubble sort làm ví dụ đầu tiên. Production thì không, educational thì yes.

10. Deep Dive

11. Tóm tắt

• Bubble sort O(n²): stable, có early exit khi sorted, nhưng thực tế chậm hơn Insertion. Dùng trong production là dấu hiệu cần refactor ngay.
• Selection sort O(n²): không adaptive, không stable, nhưng chỉ n-1 lần swap. Hữu ích khi swap đắt hơn compare.
• Insertion sort O(n²): stable, adaptive O(n+d), online — ba đặc tính khiến nó vẫn xuất hiện trong production library.
• Constants matter ở n nhỏ: Insertion sort thắng Arrays.sort khi n dưới ~47 vì không có recursion overhead.
• TimSort dùng Insertion sort để extend run ngắn — subarray nhỏ + gần sorted = Insertion sort gần O(n).
• Thứ tự điều kiện while (j >= 0 && arr[j] > key) — j >= 0 phải đứng trước để tránh ArrayIndexOutOfBoundsException.
• Selection sort không stable — không dùng cho multi-key sort mà giả định stable behavior.
• Benchmark trước khi kết luận: Arrays.sort nhanh hơn 50-100x ở n lớn, nhưng Insertion sort thắng ở n nhỏ — đây là tradeoff quan trọng nhất của bài.

12. Tự kiểm tra

Bài tiếp theo: Merge sort — divide and conquer, stable O(n log n)