PENALGO

Giao diện

Timsort — Thuật toán sắp xếp của thực tế ​

Mỗi lần bạn gọi sorted() trong Python hay Arrays.sort() trong Java, bạn đang dùng Timsort. Không phải Quick Sort. Không phải Merge Sort thuần túy. Mà là một thuật toán hybrid được Tim Peters thiết kế năm 2002 — thuật toán sắp xếp production duy nhất được sinh ra từ dữ liệu thực tế.

Điểm then chốt: dữ liệu ngoài đời hiếm khi hoàn toàn ngẫu nhiên. Log files gần như đã sắp xếp theo timestamp. Kết quả database thường có thứ tự cục bộ. Danh sách user đã nhóm theo alphabet. Timsort nhận diện và khai thác trật tự có sẵn này — biến O(n log n) lý thuyết thành O(n) thực tế khi dữ liệu đã gần sắp xếp.

Đây là thuật toán mà mọi kỹ sư cần hiểu — không phải để tự cài đặt, mà để biết tại sao standard library sort lại nhanh đến vậy, và khi nào nên tin tưởng nó hoàn toàn.

Bức tranh tư duy ​

Hãy hình dung một thầy giáo dày dặn kinh nghiệm nhận lớp mới 40 học sinh và cần xếp chỗ ngồi theo thứ tự điểm.

Thầy giáo thiếu kinh nghiệm sẽ bắt đầu từ đầu — so sánh từng cặp, sắp xếp lại toàn bộ. Nhưng thầy giáo giỏi thì khác:

  1. Quan sát trước (Detect Runs): Thầy nhìn qua lớp và nhận ra — nhóm 5 bạn bên trái đã ngồi đúng thứ tự điểm, nhóm 3 bạn ở giữa ngồi ngược (điểm cao xuống thấp, chỉ cần đảo lại). Đây là các "run" — đoạn dữ liệu đã có trật tự.
  2. Mở rộng nhóm nhỏ (Insertion Sort): Nhóm 2 bạn ngồi rải rác? Thầy xếp nhanh bằng tay — chen vào đúng vị trí trong nhóm gần nhất. Nhanh gọn vì nhóm nhỏ.
  3. Ghép nhóm thông minh (Merge): Sau khi có các nhóm đã sắp xếp, thầy ghép chúng lại — nhưng không ghép bừa. Thầy ghép hai nhóm kích thước tương đương trước, tránh tình huống ghép nhóm 20 người với nhóm 2 người (lãng phí).

Thầy giáo này thích ứng với lớp học — lớp đã ngoan (gần sorted) thì xong nhanh, lớp hỗn loạn (random) thì vẫn đảm bảo hoàn thành đúng giờ. Đó chính xác là cách Timsort hoạt động.

💡 HPN's Insight

Timsort là minh chứng rằng thuật toán tốt nhất không phải thuật toán nhanh nhất trên lý thuyết — mà là thuật toán hiểu dữ liệu thực tế. Merge Sort luôn O(n log n) dù mảng đã sorted. Quick Sort có thể rơi vào O(n²). Timsort đạt O(n) khi dữ liệu gần sorted — đúng đặc tính của phần lớn dữ liệu production.

Cốt lõi kỹ thuật ​

Bốn trụ cột của Timsort ​

Timsort kết hợp bốn kỹ thuật cốt lõi thành một hệ thống nhất:

Trụ cộtVai tròTại sao cần
Run DetectionTìm đoạn đã có trật tự (tăng hoặc giảm)Khai thác trật tự có sẵn trong dữ liệu
Minrun + Insertion SortMở rộng run ngắn đến kích thước tối thiểuInsertion Sort nhanh trên mảng nhỏ, cache-friendly
Merge với GallopingGhép các run bằng merge thông minhGalloping tăng tốc khi run có mật độ khác nhau
Stack InvariantsQuyết định thứ tự mergeĐảm bảo merge runs kích thước tương đương

Phase 1: Detect Runs — nhận diện trật tự có sẵn ​

Timsort quét mảng từ trái sang phải, tìm các đoạn liên tiếp đã có thứ tự:

  • Ascending run: a[i] <= a[i+1] (dùng <= để giữ stability)
  • Descending run: a[i] > a[i+1] (dùng > strict — đảo lại thành ascending)
text
Input:  [1, 3, 5, 9, 7, 4, 2, 6, 8, 10]

Quét từ trái:
  [1, 3, 5, 9]  → ascending run (len=4)
  [7, 4, 2]     → descending run → đảo thành [2, 4, 7] (len=3)
  [6, 8, 10]    → ascending run (len=3)

Descending run được đảo ngược in-place bằng phép swap hai đầu — O(k) với k là độ dài run.

Phase 2: Minrun — kích thước tối thiểu của run ​

Nếu run tự nhiên quá ngắn, Timsort mở rộng bằng Binary Insertion Sort cho đến khi đạt minrun. Giá trị minrun được chọn trong khoảng 32–64 sao cho n/minrun gần lũy thừa của 2 — tối ưu cho việc merge đôi sau này.

text
Công thức tính minrun:
  Bắt đầu với n (kích thước mảng)
  Lặp: dịch phải n, ghi nhận bit thấp nhất bị mất
  Khi n < 64: minrun = n + (có bit bị mất ? 1 : 0)

Ví dụ: n = 256  →  256 >> ... → minrun = 32  (256/32 = 8 = 2³ ✓)
Ví dụ: n = 100  →  100 >> ... → minrun = 50  (100/50 = 2 = 2¹ ✓)
Ví dụ: n = 2112 →  2112 >> ... → minrun = 33  (2112/33 = 64 = 2⁶ ✓)

Tại sao 32–64? Vì Insertion Sort trên mảng nhỏ (≤64 phần tử) nhanh hơn Merge Sort nhờ ít overhead và cache locality tốt. Đây là điểm giao giữa lý thuyết và thực nghiệm.

Phase 3: Merge với Galloping Mode ​

Sau khi có các run đã sắp xếp, Timsort merge chúng bằng kỹ thuật tương tự Merge Sort — nhưng với hai cải tiến quan trọng:

Galloping Mode: Khi merge hai run A và B, nếu phần tử từ A liên tục "thắng" (nhỏ hơn) nhiều lần liên tiếp (mặc định 7 lần), Timsort chuyển sang galloping — tìm vị trí đúng bằng bước nhảy lũy thừa (1, 2, 4, 8, 16...) rồi binary search.

text
Merge thông thường:  so sánh từng cặp → O(n)
  A: [1, 2, 3, 4, 5, 100, 200]
  B: [50, 60, 70, 80, 90]
  → 5 lần liên tiếp lấy từ A trước khi B thắng

Galloping mode:  nhảy lũy thừa + binary search
  A thắng liên tiếp → gallop: kiểm tra vị trí 1, 2, 4, 8...
  → Tìm ra A[0..4] đều < B[0] → copy cả block
  → Nhanh hơn nhiều khi run có mật độ chênh lệch

Memory-Efficient Merge: Chỉ copy run nhỏ hơn vào buffer tạm, merge ngược lại vào mảng gốc. Tốn O(min(|A|, |B|)) thay vì O(n).

Phase 4: Merge Stack Invariants ​

Timsort dùng stack lưu các run chưa merge. Sau mỗi lần push run mới, kiểm tra hai bất biến (với ba run trên cùng X, Y, Z):

text
Invariant 1:  |Z| > |Y| + |X|
Invariant 2:  |Y| > |X|

Nếu vi phạm → merge Y với min(X, Z) cho đến khi thỏa mãn

Bất biến này đảm bảo các run trên stack có kích thước tăng dần từ đỉnh xuống đáy (tương tự dãy Fibonacci) — tránh tình huống merge run lớn với run nhỏ (lãng phí thao tác).

Cài đặt đầy đủ ​

python
from typing import TypeVar
from bisect import insort_left

T = TypeVar('T')
MIN_MERGE = 32


def calc_minrun(n: int) -> int:
    """Tính minrun trong khoảng [32, 64] sao cho n/minrun ≈ lũy thừa 2."""
    r = 0
    while n >= MIN_MERGE:
        r |= n & 1
        n >>= 1
    return n + r


def binary_insertion_sort(arr: list, left: int, right: int, start: int) -> None:
    """
    Binary Insertion Sort cho đoạn [left, right).
    Giả sử [left, start) đã sắp xếp — chỉ chèn từ start trở đi.
    """
    for i in range(max(start, left + 1), right):
        key = arr[i]
        lo, hi = left, i
        while lo < hi:
            mid = (lo + hi) // 2
            if arr[mid] > key:
                hi = mid
            else:
                lo = mid + 1
        # Dịch phải để nhường chỗ, rồi chèn
        arr[lo + 1: i + 1] = arr[lo: i]
        arr[lo] = key


def find_run(arr: list, start: int, n: int) -> tuple[int, bool]:
    """
    Tìm run bắt đầu từ start. Trả về (run_end, was_descending).
    Ascending: a[i] <= a[i+1]. Descending: a[i] > a[i+1].
    """
    if start + 1 >= n:
        return start + 1, False

    pos = start + 1
    if arr[pos] < arr[start]:
        # Strictly descending — dùng < strict để giữ stability khi đảo
        while pos < n and arr[pos] < arr[pos - 1]:
            pos += 1
        # Đảo ngược để thành ascending
        left, right = start, pos - 1
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
        return pos, True
    else:
        # Non-descending (ascending)
        while pos < n and arr[pos] >= arr[pos - 1]:
            pos += 1
        return pos, False


def merge_low(arr: list, base1: int, len1: int, base2: int, len2: int) -> None:
    """Merge khi run trái nhỏ hơn — copy run trái vào temp."""
    temp = arr[base1: base1 + len1]
    i, j, dest = 0, base2, base1

    while i < len1 and j < base2 + len2:
        if temp[i] <= arr[j]:  # <= giữ stability
            arr[dest] = temp[i]
            i += 1
        else:
            arr[dest] = arr[j]
            j += 1
        dest += 1

    arr[dest: dest + len1 - i] = temp[i: len1]


def merge_high(arr: list, base1: int, len1: int, base2: int, len2: int) -> None:
    """Merge khi run phải nhỏ hơn — copy run phải vào temp."""
    temp = arr[base2: base2 + len2]
    i, j, dest = base1 + len1 - 1, len2 - 1, base2 + len2 - 1

    while i >= base1 and j >= 0:
        if arr[i] > temp[j]:
            arr[dest] = arr[i]
            i -= 1
        else:
            arr[dest] = temp[j]
            j -= 1
        dest -= 1

    arr[dest - j: dest + 1] = temp[0: j + 1]


def timsort(arr: list) -> None:
    """
    Timsort — thuật toán hybrid adaptive, stable.
    Best: O(n) khi đã sorted. Worst/Average: O(n log n). Space: O(n).
    """
    n = len(arr)
    if n < 2:
        return

    minrun = calc_minrun(n)
    # Stack lưu (base, length) của các run chưa merge
    run_stack: list[tuple[int, int]] = []
    pos = 0

    while pos < n:
        run_end, _ = find_run(arr, pos, n)
        run_len = run_end - pos

        # Mở rộng run ngắn bằng Binary Insertion Sort
        if run_len < minrun:
            force = min(minrun, n - pos)
            binary_insertion_sort(arr, pos, pos + force, run_end)
            run_len = force

        run_stack.append((pos, run_len))
        pos += run_len

        # Duy trì stack invariants
        while len(run_stack) > 1:
            n_runs = len(run_stack)
            if (n_runs >= 3
                    and run_stack[-3][1] <= run_stack[-2][1] + run_stack[-1][1]):
                if run_stack[-3][1] < run_stack[-1][1]:
                    _merge_at(arr, run_stack, -3)
                else:
                    _merge_at(arr, run_stack, -2)
            elif run_stack[-2][1] <= run_stack[-1][1]:
                _merge_at(arr, run_stack, -2)
            else:
                break

    # Merge hết các run còn lại trên stack
    while len(run_stack) > 1:
        _merge_at(arr, run_stack, -2)


def _merge_at(arr: list, stack: list[tuple[int, int]], idx: int) -> None:
    """Merge run tại vị trí idx với run kế tiếp trong stack."""
    base1, len1 = stack[idx]
    base2, len2 = stack[idx + 1]

    # Cập nhật stack: gộp hai run thành một
    stack[idx] = (base1, len1 + len2)
    if idx == -3 or (idx >= 0 and idx == len(stack) - 3):
        del stack[idx + 1]
    else:
        del stack[idx + 1]

    # Chọn merge_low hoặc merge_high tùy run nào nhỏ hơn
    if len1 <= len2:
        merge_low(arr, base1, len1, base2, len2)
    else:
        merge_high(arr, base1, len1, base2, len2)
java
import java.util.Arrays;

public class Timsort {
    private static final int MIN_MERGE = 32;

    static int calcMinrun(int n) {
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    static void binaryInsertionSort(int[] arr, int left, int right, int start) {
        for (int i = Math.max(start, left + 1); i < right; i++) {
            int key = arr[i];
            int lo = left, hi = i;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (arr[mid] > key) hi = mid;
                else lo = mid + 1;
            }
            System.arraycopy(arr, lo, arr, lo + 1, i - lo);
            arr[lo] = key;
        }
    }

    /**
     * Tìm run ascending/descending. Đảo descending run.
     * Trả về vị trí kết thúc run.
     */
    static int findRun(int[] arr, int start, int n) {
        if (start + 1 >= n) return start + 1;

        int pos = start + 1;
        if (arr[pos] < arr[start]) {
            while (pos < n && arr[pos] < arr[pos - 1]) pos++;
            // Đảo descending → ascending
            for (int l = start, r = pos - 1; l < r; l++, r--) {
                int tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp;
            }
        } else {
            while (pos < n && arr[pos] >= arr[pos - 1]) pos++;
        }
        return pos;
    }

    static void merge(int[] arr, int base1, int len1, int base2, int len2) {
        // Copy run nhỏ hơn vào temp
        int[] temp = Arrays.copyOfRange(arr, base1, base1 + len1);
        int i = 0, j = base2, dest = base1;

        while (i < len1 && j < base2 + len2) {
            if (temp[i] <= arr[j]) {  // <= giữ stability
                arr[dest++] = temp[i++];
            } else {
                arr[dest++] = arr[j++];
            }
        }
        System.arraycopy(temp, i, arr, dest, len1 - i);
    }

    public static void sort(int[] arr) {
        int n = arr.length;
        if (n < 2) return;

        int minrun = calcMinrun(n);
        // Sử dụng stack đơn giản lưu (base, len)
        int[][] runStack = new int[85][2]; // log2(Integer.MAX_VALUE) + buffer
        int stackSize = 0;
        int pos = 0;

        while (pos < n) {
            int runEnd = findRun(arr, pos, n);
            int runLen = runEnd - pos;

            if (runLen < minrun) {
                int force = Math.min(minrun, n - pos);
                binaryInsertionSort(arr, pos, pos + force, runEnd);
                runLen = force;
            }

            runStack[stackSize][0] = pos;
            runStack[stackSize][1] = runLen;
            stackSize++;
            pos += runLen;

            // Duy trì merge stack invariants
            while (stackSize > 1) {
                int i2 = stackSize - 1, i1 = i2 - 1, i0 = i1 - 1;
                if (stackSize >= 3 && runStack[i0][1] <= runStack[i1][1] + runStack[i2][1]) {
                    if (runStack[i0][1] < runStack[i2][1]) {
                        merge(arr, runStack[i0][0], runStack[i0][1],
                              runStack[i1][0], runStack[i1][1]);
                        runStack[i0][1] += runStack[i1][1];
                        runStack[i1] = runStack[i2];
                    } else {
                        merge(arr, runStack[i1][0], runStack[i1][1],
                              runStack[i2][0], runStack[i2][1]);
                        runStack[i1][1] += runStack[i2][1];
                    }
                    stackSize--;
                } else if (runStack[i1][1] <= runStack[i2][1]) {
                    merge(arr, runStack[i1][0], runStack[i1][1],
                          runStack[i2][0], runStack[i2][1]);
                    runStack[i1][1] += runStack[i2][1];
                    stackSize--;
                } else {
                    break;
                }
            }
        }

        while (stackSize > 1) {
            int i2 = stackSize - 1, i1 = i2 - 1;
            merge(arr, runStack[i1][0], runStack[i1][1],
                  runStack[i2][0], runStack[i2][1]);
            runStack[i1][1] += runStack[i2][1];
            stackSize--;
        }
    }
}
cpp
#include <vector>
#include <algorithm>
using namespace std;

const int MIN_MERGE = 32;

int calcMinrun(int n) {
    int r = 0;
    while (n >= MIN_MERGE) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

void binaryInsertionSort(vector<int>& arr, int left, int right, int start) {
    for (int i = max(start, left + 1); i < right; i++) {
        int key = arr[i];
        int lo = left, hi = i;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > key) hi = mid;
            else lo = mid + 1;
        }
        // Dịch phải rồi chèn
        for (int j = i; j > lo; j--)
            arr[j] = arr[j - 1];
        arr[lo] = key;
    }
}

// Tìm run, đảo descending. Trả về vị trí kết thúc.
int findRun(vector<int>& arr, int start, int n) {
    if (start + 1 >= n) return start + 1;

    int pos = start + 1;
    if (arr[pos] < arr[start]) {
        while (pos < n && arr[pos] < arr[pos - 1]) pos++;
        reverse(arr.begin() + start, arr.begin() + pos);
    } else {
        while (pos < n && arr[pos] >= arr[pos - 1]) pos++;
    }
    return pos;
}

void mergeRuns(vector<int>& arr, int base1, int len1, int base2, int len2) {
    vector<int> temp(arr.begin() + base1, arr.begin() + base1 + len1);
    int i = 0, j = base2, dest = base1;

    while (i < len1 && j < base2 + len2) {
        if (temp[i] <= arr[j])  // <= giữ stability
            arr[dest++] = temp[i++];
        else
            arr[dest++] = arr[j++];
    }
    copy(temp.begin() + i, temp.end(), arr.begin() + dest);
}

void timsort(vector<int>& arr) {
    int n = arr.size();
    if (n < 2) return;

    int minrun = calcMinrun(n);
    // Stack lưu (base, length) — tối đa ~85 entries cho INT_MAX
    vector<pair<int,int>> runStack;
    int pos = 0;

    while (pos < n) {
        int runEnd = findRun(arr, pos, n);
        int runLen = runEnd - pos;

        if (runLen < minrun) {
            int force = min(minrun, n - pos);
            binaryInsertionSort(arr, pos, pos + force, runEnd);
            runLen = force;
        }

        runStack.push_back({pos, runLen});
        pos += runLen;

        // Duy trì stack invariants
        while (runStack.size() > 1) {
            int sz = runStack.size();
            auto& x = runStack[sz - 1];
            auto& y = runStack[sz - 2];
            if (sz >= 3) {
                auto& z = runStack[sz - 3];
                if (z.second <= y.second + x.second) {
                    if (z.second < x.second) {
                        mergeRuns(arr, z.first, z.second, y.first, y.second);
                        z.second += y.second;
                        runStack[sz - 2] = runStack[sz - 1];
                    } else {
                        mergeRuns(arr, y.first, y.second, x.first, x.second);
                        y.second += x.second;
                    }
                    runStack.pop_back();
                    continue;
                }
            }
            if (y.second <= x.second) {
                mergeRuns(arr, y.first, y.second, x.first, x.second);
                y.second += x.second;
                runStack.pop_back();
            } else {
                break;
            }
        }
    }

    while (runStack.size() > 1) {
        int sz = runStack.size();
        auto& x = runStack[sz - 1];
        auto& y = runStack[sz - 2];
        mergeRuns(arr, y.first, y.second, x.first, x.second);
        y.second += x.second;
        runStack.pop_back();
    }
}

🎓 HPN's Comparison: Timsort vs Merge Sort thuần

Merge Sort luôn chia đôi mù quáng — kể cả khi mảng đã sorted. Timsort nhận diện trật tự có sẵn, chỉ chia và merge khi cần. Trên mảng 1 triệu phần tử đã sorted, Merge Sort vẫn thực hiện ~20 triệu phép so sánh. Timsort? Chỉ ~1 triệu lần quét — gần O(n). Đó là sức mạnh của adaptive algorithm.

Thực chiến ​

Tại sao standard library chọn Timsort ​

Từ 2002, Timsort đã trở thành thuật toán sort mặc định trong hàng loạt ngôn ngữ production:

Ngôn ngữHàmTimsort?Ghi chú
Pythonlist.sort(), sorted()✅CPython implementation gốc
JavaArrays.sort(Object[])✅Từ JDK 7 (2011). Primitive dùng Dual-Pivot QuickSort
Rustslice::sort()✅Biến thể merge-based, stable
SwiftArray.sort()✅Introsort cho unstable, Timsort cho stable
AndroidJava Collections✅Theo Java spec

Lý do: dữ liệu thực tế trong production hiếm khi random. Log entries gần sorted theo thời gian. Database rows có cluster index. User lists nhóm theo locale. Timsort khai thác đặc tính này — và trong benchmarks thực tế, nó thắng QuickSort trên dữ liệu có cấu trúc.

Benchmarking: sorted() vs cài đặt thủ công ​

python
import time
import random

def benchmark_on_distributions(n: int = 100_000, trials: int = 20):
    """So sánh built-in sort trên các phân bố dữ liệu khác nhau."""
    distributions = {
        "Random":         lambda: [random.randint(0, n) for _ in range(n)],
        "Nearly sorted":  lambda: _nearly_sorted(n),
        "Reversed":       lambda: list(range(n, 0, -1)),
        "Few unique":     lambda: [random.randint(0, 10) for _ in range(n)],
        "Already sorted": lambda: list(range(n)),
    }

    for name, gen in distributions.items():
        total = 0.0
        for _ in range(trials):
            data = gen()
            start = time.perf_counter()
            data.sort()  # Timsort bên trong
            total += time.perf_counter() - start
        avg_ms = total / trials * 1000
        print(f"{name:20s}: {avg_ms:8.2f} ms")


def _nearly_sorted(n: int) -> list[int]:
    arr = list(range(n))
    # Xáo trộn 5% phần tử
    for _ in range(n // 20):
        i, j = random.randint(0, n - 1), random.randint(0, n - 1)
        arr[i], arr[j] = arr[j], arr[i]
    return arr


# Kết quả điển hình (n=100,000):
# Random              :    12.45 ms
# Nearly sorted       :     3.21 ms  ← Timsort tận dụng trật tự có sẵn
# Reversed            :     2.87 ms  ← Một descending run duy nhất → đảo → done
# Few unique          :     4.52 ms  ← Nhiều run tự nhiên
# Already sorted      :     1.08 ms  ← Gần O(n): chỉ quét, không merge

⚡ ENGINEERING DEEP DIVE: Khi nào sorted() gần O(n)?

Timsort đạt hiệu năng gần O(n) khi:

  1. Dữ liệu đã sorted → một run duy nhất, không cần merge
  2. Dữ liệu gần sorted → ít run lớn, ít merge
  3. Dữ liệu reversed → một descending run → đảo O(n) → xong
  4. Dữ liệu là concat của vài mảng sorted → vài run lớn, merge nhanh

Đây chính xác là đặc tính của log files, time-series data, database query results, và event streams — dữ liệu mà bạn sort hàng ngày trong production.

Ứng dụng thực tế: sort stability trong production ​

Stability — giữ thứ tự gốc cho phần tử bằng nhau — là yêu cầu thiết yếu khi sort multi-key:

python
# Ví dụ production: sort đơn hàng theo ưu tiên, giữ thứ tự thời gian
orders = [
    {"id": "A1", "priority": 2, "created": "09:00"},
    {"id": "A2", "priority": 1, "created": "09:05"},
    {"id": "A3", "priority": 2, "created": "09:10"},
    {"id": "A4", "priority": 1, "created": "09:15"},
]

# Stable sort theo priority → đơn hàng cùng priority giữ thứ tự created
sorted_orders = sorted(orders, key=lambda o: o["priority"])
# Kết quả: A2(p1, 09:05), A4(p1, 09:15), A1(p2, 09:00), A3(p2, 09:10)
# ✅ Trong cùng priority, thứ tự thời gian được bảo toàn

# Unstable sort (như QuickSort) có thể cho:
# A4(p1, 09:15), A2(p1, 09:05), ... → SAI thứ tự thời gian

Sai lầm điển hình ​

❌ Sai lầm 1: Tự cài đặt Timsort thay vì dùng standard library ​

🛑 HPN's Warning

Timsort trong CPython có ~2400 dòng C được tối ưu suốt hơn 20 năm. Java's implementation cũng tương đương. Tự viết lại từ đầu không chỉ chậm hơn 10-50x mà còn gần như chắc chắn có bug — kể cả implementation của Java cũng từng bị tìm thấy lỗi sau 9 năm (xem phần Under the Hood).

python
# ❌ SAI: Viết timsort thủ công cho production
def my_timsort(arr):
    # 500 dòng code, thiếu galloping, sai invariant...
    pass

result = my_timsort(data)

# ✅ ĐÚNG: Dùng built-in — nó đã là Timsort, được test với hàng tỷ lần gọi
result = sorted(data)                      # Python
# Arrays.sort(arr);                        // Java
# std::stable_sort(arr.begin(), arr.end()) // C++ (merge-sort based, tương tự)

Khi nào cần cài đặt thủ công? Chỉ khi: (a) ngôn ngữ không có stable sort trong stdlib, (b) bạn cần sort trên cấu trúc dữ liệu custom (linked list, external storage), hoặc (c) trong cuộc phỏng vấn.

❌ Sai lầm 2: Nghĩ rằng mọi O(n log n) sort đều nhanh như nhau ​

text
Lý thuyết:   QuickSort = MergeSort = Timsort = HeapSort = O(n log n)
Thực tế trên 1 triệu phần tử gần sorted:

  Timsort:    ~15 ms  ← adaptive, khai thác trật tự có sẵn
  MergeSort:  ~85 ms  ← luôn chia đôi mù quáng
  QuickSort:  ~70 ms  ← không nhận diện pattern
  HeapSort:  ~120 ms  ← cache-unfriendly, constant factor cao

Hằng số ẩn trong Big-O khác nhau RẤT LỚN trên dữ liệu thực tế.

Big-O chỉ cho biết tốc độ tăng trưởng — không cho biết thời gian chạy thực tế. Timsort có constant factor thấp hơn trên dữ liệu có cấu trúc nhờ adaptive behavior.

❌ Sai lầm 3: Không hiểu tại sao sorted() nhanh trên dữ liệu "gần sorted" ​

Nhiều kỹ sư sort một list rồi thêm phần tử mới, rồi sort lại toàn bộ — và thấy "nhanh bất thường". Đó không phải magic — đó là Timsort nhận ra mảng gần sorted và chạy gần O(n).

python
# Pattern phổ biến trong production
events = []  # đã sorted theo timestamp

# Thêm batch mới (cũng đã sorted)
events.extend(new_batch)

# Sort lại toàn bộ — Timsort nhận ra hai run lớn đã sorted
# → merge một lần → gần O(n) thay vì O(n log n)
events.sort(key=lambda e: e.timestamp)

Hiểu behavior này giúp bạn thiết kế hệ thống tận dụng Timsort — ví dụ maintain sorted order bằng sort() sau mỗi batch insert thay vì dùng cấu trúc phức tạp hơn.

❌ Sai lầm 4: Bỏ qua yêu cầu stability khi chọn thuật toán sort ​

python
# ❌ SAI: Dùng unstable sort cho multi-key sorting
# (C++ std::sort, không đảm bảo stability)
# students sort theo GPA, rồi sort theo tên
# → thứ tự GPA bị phá vỡ cho cùng tên

# ✅ ĐÚNG: Dùng stable sort — Timsort đảm bảo
students.sort(key=lambda s: s.gpa)      # sort GPA trước
students.sort(key=lambda s: s.name)     # sort tên sau — GPA order giữ nguyên

# Hoặc tốt hơn — sort bằng tuple key:
students.sort(key=lambda s: (s.name, s.gpa))

⚠️ Cạm bẫy phổ biến

Trong C++, std::sort là unstable (thường dùng Introsort). Nếu cần stability, phải dùng std::stable_sort. Trong Java, Arrays.sort(int[]) dùng Dual-Pivot QuickSort (unstable), nhưng Arrays.sort(Object[]) dùng Timsort (stable). Biết sự khác biệt này tránh được bug khó debug trong production.

Under the Hood ​

Phân tích độ phức tạp ​

Trường hợpTimeSpaceGhi chú
BestO(n)O(n)Mảng đã sorted — một run duy nhất, chỉ quét
AverageO(n log n)O(n)Dữ liệu hỗn hợp
WorstO(n log n)O(n)Dữ liệu hoàn toàn random
Nearly sortedO(n log r)O(n)r = số run tự nhiên (r ≪ n)

Trong đó, O(n) space cho merge buffer (chỉ cần O(min(run1, run2)) cho mỗi lần merge, nhưng worst case vẫn là O(n/2) ≈ O(n)).

Galloping Mode — phân tích chi tiết ​

Galloping hoạt động theo hai bước:

  1. Exponential search: Kiểm tra vị trí 1, 2, 4, 8, 16... cho đến khi vượt quá target
  2. Binary search: Tìm chính xác trong khoảng đã xác định
text
Merge A = [1, 2, 3, ..., 1000] với B = [1001, 1002, ..., 2000]

Linear merge:  1000 phép so sánh (mỗi phần tử A đều < mọi phần tử B)
Galloping:     ~10 phép so sánh (nhảy 1, 2, 4, ..., 1024 → vượt → binary search)

Tiết kiệm: ~99% phép so sánh khi run có mật độ chênh lệch lớn

Timsort tự động bật/tắt galloping dựa trên hiệu quả thực tế. Nếu galloping không tiết kiệm đủ (threshold mặc định = 7 lần thắng liên tiếp), nó quay lại linear merge. Adaptive behavior này tránh overhead của galloping trên dữ liệu interleaved đều.

Merge Stack Invariants và bug 2015 ​

Năm 2015, nhóm nghiên cứu từ Đại học Radboud (Hà Lan) dùng formal verification phát hiện bug trong Java's Timsort — tồn tại suốt 9 năm mà không ai biết.

text
Bug: Stack có thể overflow nếu merge invariants chỉ kiểm tra 3 run trên cùng

Invariant gốc (Tim Peters 2002):
  Chỉ kiểm tra: |C| > |B| + |A|  và  |B| > |A|
  → Trong trường hợp hiếm, run sâu hơn trong stack vi phạm invariant
  → Stack cần nhiều entries hơn dự kiến → ArrayIndexOutOfBoundsException

Fix: Kiểm tra invariant cho TẤT CẢ run trên stack, không chỉ 3 run trên cùng

Bug này chỉ trigger với mảng kích thước rất lớn (hàng chục triệu phần tử) và phân bố đặc biệt — nên không bị phát hiện trong thực tế. Nhưng nó minh họa rằng kể cả thuật toán production cũng có thể chứa bug subtile mà chỉ formal verification mới tìm được.

Cách chọn minrun — lý do toán học ​

Minrun được chọn trong [32, 64] sao cho n/minrun gần lũy thừa 2:

text
Tại sao lũy thừa 2?
  Merge hoạt động tốt nhất khi hai run có kích thước BẰNG NHAU.
  Nếu n/minrun = 2^k, thì sau k tầng merge, mọi run đều bằng nhau.

  n = 256, minrun = 32  → 8 run × 32  → 4 run × 64 → 2 × 128 → 1 × 256
  n = 100, minrun = 50  → 2 run × 50  → 1 × 100  (merge đối xứng hoàn hảo)

Nếu minrun chọn sai (n/minrun không gần 2^k):
  n = 256, minrun = 33  → 7.75 run → run cuối chỉ 25 → merge bất đối xứng → chậm hơn

Hiệu năng trên các phân bố dữ liệu ​

Phân bốSố comparisons (n=10⁶)So với n log nGiải thích
Đã sorted~n~0.05xMột run, không merge
Gần sorted (5% xáo trộn)~3n~0.15xÍt run lớn
Random~n log n1.0xKhông có run tự nhiên
Reversed~n~0.05xMột desc run → đảo
Pipe organ (tăng rồi giảm)~2n~0.10xHai run
Many duplicates~0.5n log n~0.5xNhiều run tự nhiên từ equal elements

💡 HPN's Insight

Timsort là thuật toán natural merge sort — thuật ngữ chỉ các merge sort adaptive. Hiệu năng tỷ lệ với entropy (mức độ hỗn loạn) của dữ liệu, không phải kích thước. Dữ liệu production có entropy thấp (gần sorted) → Timsort nhanh. Dữ liệu random có entropy cao → Timsort vẫn O(n log n), không tệ hơn.

Checklist ghi nhớ ​

✅ Checklist triển khai

Kiến trúc Timsort

  • [ ] Timsort = Run detection + Insertion Sort + Merge Sort + Galloping
  • [ ] Run là đoạn liên tiếp đã tăng (<=) hoặc giảm (>), descending run được đảo ngược
  • [ ] Minrun nằm trong [32, 64], chọn sao cho n/minrun gần lũy thừa 2

Hiệu năng & Đặc tính

  • [ ] Best O(n) trên dữ liệu đã sorted — adaptive, không như Merge Sort thuần (luôn O(n log n))
  • [ ] Worst/Average O(n log n), Space O(n) — worst case không bao giờ xấu hơn Merge Sort
  • [ ] Stable sort — giữ thứ tự gốc cho phần tử bằng nhau, thiết yếu cho multi-key sort

Kỹ thuật tối ưu

  • [ ] Galloping mode tăng tốc merge khi run có mật độ chênh lệch lớn
  • [ ] Stack invariants đảm bảo merge runs kích thước tương đương, tránh merge bất đối xứng

Quy tắc production

  • [ ] LUÔN dùng built-in sort() — nó đã là Timsort, được tối ưu hàng thập kỷ
  • [ ] Phân biệt stable vs unstable sort trong ngôn ngữ bạn dùng (Java primitive vs Object sort)

Bài tập luyện tập ​

Bài 1: Detect Natural Runs — Foundation ​

Đề bài: Cho mảng số nguyên, viết hàm đếm số natural runs (đoạn tăng hoặc giảm liên tiếp). Descending runs cũng tính là một run. Trả về số lượng run.

Ví dụ:

text
Input:  [1, 3, 5, 9, 7, 4, 2, 6, 8, 10]
Output: 3
Giải thích: Run 1: [1,3,5,9]↑  Run 2: [9,7,4,2]↓  Run 3: [2,6,8,10]↑
💡 Gợi ý
  • Quét từ trái sang phải, xác định chiều (tăng/giảm) tại mỗi vị trí
  • Khi chiều thay đổi (từ tăng sang giảm hoặc ngược lại), đó là điểm bắt đầu run mới
  • Chú ý xử lý phần tử bằng nhau — ascending dùng <=, descending dùng >
✅ Lời giải
python
def count_natural_runs(arr: list[int]) -> int:
    """Đếm số natural runs (ascending hoặc descending) trong mảng."""
    n = len(arr)
    if n <= 1:
        return max(n, 0)  # mảng rỗng = 0 run, 1 phần tử = 1 run

    runs = 1
    pos = 1

    while pos < n:
        if arr[pos] < arr[pos - 1]:
            # Descending run
            while pos < n and arr[pos] < arr[pos - 1]:
                pos += 1
        else:
            # Ascending run (bao gồm equal)
            while pos < n and arr[pos] >= arr[pos - 1]:
                pos += 1

        if pos < n:
            runs += 1
            pos += 1  # bắt đầu run mới từ phần tử hiện tại

    return runs

Phân tích: Time O(n), Space O(1). Đây là bước đầu tiên trong Timsort — hiểu cách đếm run giúp bạn nắm được tại sao Timsort adaptive.

Bài 2: Adaptive Merge — Intermediate ​

Đề bài: Cho mảng là kết quả nối (concatenate) k mảng đã sorted. Sắp xếp mảng này trong O(n log k) bằng cách tận dụng cấu trúc run có sẵn. Dùng min-heap cho k-way merge.

Ví dụ:

text
Input:  [1, 5, 9, 2, 4, 8, 3, 6, 7]  (3 mảng sorted nối lại)
        Run 1: [1,5,9]  Run 2: [2,4,8]  Run 3: [3,6,7]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
💡 Gợi ý
  • Bước 1: Quét mảng để tìm boundaries giữa các run (tương tự Bài 1)
  • Bước 2: Dùng heapq với k pointer (một cho mỗi run) để merge
  • Min-heap chứa (giá_trị, run_index, vị_trí_trong_run)
✅ Lời giải
python
import heapq


def adaptive_merge_sort(arr: list[int]) -> list[int]:
    """
    Sort mảng bằng cách detect runs rồi k-way merge.
    O(n log k) với k = số run.
    """
    n = len(arr)
    if n <= 1:
        return arr[:]

    # Phase 1: Detect runs (tìm boundaries)
    runs: list[tuple[int, int]] = []  # (start, end) exclusive
    pos = 0
    while pos < n:
        start = pos
        pos += 1
        if pos < n and arr[pos] < arr[start]:
            while pos < n and arr[pos] < arr[pos - 1]:
                pos += 1
            # Đảo descending run
            arr[start:pos] = arr[start:pos][::-1]
        else:
            while pos < n and arr[pos] >= arr[pos - 1]:
                pos += 1
        runs.append((start, pos))

    if len(runs) == 1:
        return arr[:]

    # Phase 2: K-way merge bằng min-heap
    result: list[int] = []
    # Heap: (giá_trị, run_idx, vị_trí_hiện_tại)
    heap: list[tuple[int, int, int]] = []

    for i, (start, end) in enumerate(runs):
        heapq.heappush(heap, (arr[start], i, start))

    while heap:
        val, run_idx, pos_in_arr = heapq.heappop(heap)
        result.append(val)

        next_pos = pos_in_arr + 1
        if next_pos < runs[run_idx][1]:
            heapq.heappush(heap, (arr[next_pos], run_idx, next_pos))

    return result

Phân tích: Time O(n log k) với k = số run. Space O(n + k). Khi k nhỏ (dữ liệu gần sorted), hiệu năng gần O(n). Đây là nguyên lý cốt lõi đằng sau adaptive sorting — và cũng là cách external merge sort hoạt động trong database.

🧠 Quiz

Câu hỏi kiểm tra: Timsort đạt O(n) best-case nhờ đặc điểm nào?

  • [ ] A. Sử dụng QuickSort cho mảng nhỏ
  • [x] B. Nhận diện run (đoạn đã sorted) trong dữ liệu và chỉ merge khi cần
  • [ ] C. Dùng radix sort cho số nguyên
  • [ ] D. Chia mảng thành các phần bằng nhau rồi merge

Giải thích: Timsort đạt O(n) khi mảng đã sorted vì toàn bộ mảng là một run duy nhất — chỉ cần quét qua một lần để xác nhận, không cần merge. Đây là tính adaptive — hiệu năng tỷ lệ thuận với mức độ hỗn loạn của dữ liệu, không phải kích thước. A sai vì Timsort dùng Insertion Sort (không phải Quick Sort). C sai vì Timsort là comparison-based. D mô tả Merge Sort thuần (luôn O(n log n)).

Liên kết học tiếp ​

📚 Bài liên quan

Bài liên quan trong Penalgo

Professional Engineering Standards | © 2025 HPN Corporation