Thuật toán sắp xếpSorting Algorithms

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Sắp xếp là việc sắp lại một tập dữ liệu theo một thứ tự xác định dựa trên một toán tử so sánh. Định nghĩa đó nghe rất hẹp, và chủ đề này trông như một bảo tàng những món đồ cổ — chẳng ai đem bubble sort lên production cả. Vậy mà sắp xếp lại là bài toán được nghiên cứu nhiều nhất trong ngành, và nó xứng đáng với sự chú ý đó vì ba lý do.

Thứ nhất, sắp xếp là bước tiền xử lý biến các bài toán khác thành dễ. Một array đã sắp xếp hỗ trợ binary search ở O(log n) (./09-search-algorithms.md), biến việc phát hiện trùng lặp thành một lần quét tuyến tính, biến “tìm trung vị” thành một phép truy cập index, biến việc gộp interval thành chuyện hiển nhiên, và biến nhiều vòng lặp brute-force O(n²) thành các lần quét O(n log n). Hình dáng thường thấy của một lời giải hiệu quả là sort, rồi duyệt một lượt.

Thứ hai, các thuật toán sắp xếp là một danh mục các paradigm thuật toán chính ở dạng rõ ràng nhất. Insertion sort là xây dựng tăng dần. Merge sort và quicksort là divide and conquer (./19-recursion-and-divide-and-conquer.md). Heap sort là “dựng đúng cấu trúc dữ liệu thì thuật toán tự rơi ra” (./12-heaps-and-priority-queues.md). Counting sort là đổi bộ nhớ lấy thời gian. Học sáu thuật toán sắp xếp dạy bạn nhiều về thiết kế thuật toán hơn là học sáu bài toán không liên quan tới nhau.

Thứ ba, sắp xếp là nơi khoảng cách giữa lý thuyết và thực tế lộ ra rõ nhất. Có một cận dưới Ω(n log n) đã được chứng minh cho các comparison sort — vậy mà các thư viện thật vẫn vượt qua nó trong trường hợp đặc biệt, né hoàn toàn nó với số nguyên, và dùng insertion sort O(n²) cho các subarray nhỏ vì ở quy mô đó hằng số nhân và hành vi cache mới là thứ quyết định. Hiểu tại sao Timsort, introsort và pdqsort lại có hình dáng như vậy có ích hơn bất kỳ thuật toán đơn lẻ nào.

Hai tính chất xuất hiện xuyên suốt và đáng định nghĩa ngay từ đầu:

• Stable — các phần tử bằng nhau giữ nguyên thứ tự tương đối như trong input. Nếu bạn sort nhân viên theo tên rồi sort theo phòng ban, một sort stable sẽ để mỗi phòng ban vẫn được xếp theo alphabet của tên. Sort không stable sẽ làm xáo trộn. Tính stable là thứ khiến việc sort theo nhiều key có thể ghép nối được.
• In-place — chỉ dùng O(1) (hoặc O(log n)) bộ nhớ phụ ngoài array input, thay vì cấp phát thêm một array cỡ n.

Kiến thức nền tảng

Bộ ba bậc hai

Ba thuật toán này đều là O(n²). Bạn sẽ không triển khai chúng làm thuật toán sort chính, nhưng riêng insertion sort thì nằm bên trong mọi sort production, và hiểu cả ba gần như không tốn gì.

Bubble sort

Liên tục đi qua array và hoán đổi các cặp liền kề sai thứ tự. Sau lượt thứ i, i phần tử lớn nhất đã “nổi” lên cuối và nằm đúng vị trí cuối cùng.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        # Sau lượt i, i phần tử cuối đã nằm đúng vị trí cuối cùng,
        # nên vòng lặp trong có thể thu hẹp lại.
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:        # không có gì di chuyển: đã sắp xếp — best case O(n)
            break
    return arr

Độ phức tạp: O(n²) trung bình và worst case (n(n−1)/2 phép so sánh), best case O(n) chỉ khi có cờ swapped, bộ nhớ O(1), stable (nó chỉ hoán đổi các phần tử liền kề thực sự sai thứ tự). Trong thực tế nó chậm nhất trong ba thuật toán vì thực hiện nhiều lần hoán đổi nhất — mỗi cặp nghịch thế đều tốn một lần ghi. Ưu điểm duy nhất là dễ giải thích và phát hiện array đã sắp xếp chỉ trong một lượt.

Selection sort

Liên tục chọn phần tử nhỏ nhất trong phần đuôi chưa sắp xếp và hoán đổi nó về đúng chỗ.

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):        # quét phần đuôi chưa sắp để tìm min
            if arr[j] < arr[m]:
                m = j
        arr[i], arr[m] = arr[m], arr[i]  # đúng một lần hoán đổi mỗi lượt
    return arr

Độ phức tạp: O(n²) trong mọi trường hợp — việc quét tìm min luôn diễn ra bất kể input, nên không có best case. Bộ nhớ O(1). Không stable: phép hoán đổi đường dài có thể nhảy một phần tử qua một phần tử bằng nó ([2a, 2b, 1] → [1, 2b, 2a]).

Nó có một ngách ứng dụng thật sự: nó thực hiện đúng n−1 lần hoán đổi, mức tối thiểu có thể. Khi ghi đắt hơn đọc rất nhiều — EEPROM, flash memory với số chu kỳ xóa giới hạn, hoặc khi phải di chuyển các bản ghi lớn về mặt vật lý — O(n) lần ghi của selection sort thắng O(n²) lần ghi của insertion sort. (Cycle sort đẩy ý tưởng này tới cực hạn với số lần ghi tối thiểu đã được chứng minh.)

Insertion sort

Mở rộng dần một tiền tố đã sắp xếp, mỗi lần chèn một phần tử mới vào đúng vị trí bằng cách đẩy các phần tử lớn hơn sang phải. Đây chính là cách con người sắp bài trên tay.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Đẩy mọi phần tử lớn hơn hẳn `key` sang phải một ô.
        # Dấu `>` (chứ không phải `>=`) giữ nguyên thứ tự các phần tử bằng nhau,
        # và đó chính là điều làm cho insertion sort stable.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

Độ phức tạp: O(n²) trung bình và worst case (input sắp ngược khiến mọi lần đều phải đẩy toàn bộ), nhưng O(n) với input đã sắp hoặc gần sắp — vòng while bên trong thoát ngay lập tức. Chính xác hơn, nó là O(n + I) với I là số cặp nghịch thế, điều này khiến nó adaptive. Bộ nhớ O(1), stable, in-place.

Chính tính adaptive cộng với hằng số nhân rất nhỏ là lý do insertion sort là base case của gần như mọi thuật toán sort production: dưới ngưỡng khoảng 16–32 phần tử, nó thắng hẳn merge sort và quicksort, vì không có chi phí đệ quy, không cấp phát bộ nhớ, và cache locality hoàn hảo. Nó cũng là thuật toán online — có thể sort một stream ngay khi phần tử tới, điều mà không thuật toán nào khác ở đây làm được.

Divide and conquer: merge sort

Chia array làm đôi, sort đệ quy từng nửa, rồi merge hai nửa đã sắp trong thời gian tuyến tính.

                 [38, 27, 43, 3, 9, 82, 10]
                 /                        \
        [38, 27, 43]                  [3, 9, 82, 10]
        /          \                  /            \
    [38]      [27, 43]           [3, 9]        [82, 10]
              /     \            /    \         /    \
           [27]     [43]      [3]     [9]    [82]    [10]
              \     /            \    /         \    /
              [27, 43]           [3, 9]        [10, 82]
        \          /                  \            /
        [27, 38, 43]                  [3, 9, 10, 82]
                 \                        /
                 [3, 9, 10, 27, 38, 43, 82]

def merge_sort(arr):
    if len(arr) <= 1:                  # base case: 0 hoặc 1 phần tử là đã sắp xếp
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def _merge(left, right):
    """Trộn hai list đã sắp thành một list đã sắp. O(len(left) + len(right))."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        # Dùng `<=` thay vì `<` chính là thứ làm merge sort stable: khi bằng nhau,
        # phần tử ở nửa trái — phần tử xuất hiện trước — được lấy trước.
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])               # một trong hai lệnh này thao tác trên list rỗng
    out.extend(right[j:])
    return out

Độ phức tạp: O(n log n) trong mọi trường hợp. Cây đệ quy có log₂ n tầng và mỗi tầng làm O(n) công việc merge; công thức truy hồi T(n) = 2T(n/2) + O(n) cho nghiệm Θ(n log n) theo Master Theorem. Bộ nhớ là O(n) cho các buffer merge — đây là điểm yếu thật sự duy nhất của merge sort, và là lý do nó thua quicksort ở vai trò thuật toán sort mặc định trong bộ nhớ.

Điểm mạnh của merge sort nằm đúng vào chỗ quicksort yếu:

• Bảo đảm O(n log n) — không input độc hại nào làm nó suy biến được.
• Stable, đó là lý do nó (dưới dạng Timsort) là thuật toán sort cho object trong Python và Java.
• Chỉ cần truy cập tuần tự — nó không bao giờ cần random access, nên là thuật toán dành cho linked list (./05-linked-lists.md) và cho external sorting: dữ liệu quá lớn so với RAM được sort theo từng chunk, ghi ra đĩa, rồi merge bằng k-way merge điều khiển bởi một heap. Giai đoạn shuffle-and-sort của mọi framework big data đều là một merge sort phân tán (../../data-engineer/vi/10-big-data-and-distributed-computing.md).

Divide and conquer: quicksort

Chọn một pivot, phân hoạch array sao cho mọi phần tử nhỏ hơn nằm bên trái và lớn hơn nằm bên phải, rồi đệ quy vào hai bên. Khác merge sort, toàn bộ công việc nằm ở bước chia, còn bước gộp thì miễn phí.

import random


def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    while lo < hi:
        p = _partition(arr, lo, hi)
        # Đệ quy vào nửa nhỏ hơn và lặp trên nửa lớn hơn. Cách này giữ độ sâu
        # đệ quy ở O(log n) ngay cả khi phân hoạch bị lệch.
        if p - lo < hi - p:
            quick_sort(arr, lo, p - 1)
            lo = p + 1
        else:
            quick_sort(arr, p + 1, hi)
            hi = p - 1
    return arr


def _partition(arr, lo, hi):
    """Phân hoạch Lomuto với pivot chọn ngẫu nhiên.
    Trả về chỉ số mà pivot dừng lại — đúng vị trí cuối cùng của nó."""
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]      # đưa pivot ra cuối cho gọn
    pivot = arr[hi]
    i = lo                                 # bất biến: arr[lo:i] < pivot
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]      # đưa pivot về đúng chỗ
    return i

Độ phức tạp: O(n log n) trung bình, O(n²) worst case, bộ nhớ O(log n) (chỉ là recursion stack — phân hoạch diễn ra in-place). Không stable, vì phân hoạch hoán đổi các phần tử ở khoảng cách xa.

Worst case xảy ra khi pivot luôn là phần tử nhỏ nhất hoặc lớn nhất, khiến mỗi lần phân hoạch chỉ bóc ra được một phần tử và đệ quy sâu n tầng: T(n) = T(n−1) + O(n) = O(n²). Với pivot cố định là “phần tử đầu tiên”, input đã sắp xếp chính là worst case — một tính chất cực kỳ tệ, vì dữ liệu đã sắp hoặc gần sắp là cực kỳ phổ biến trong thực tế. Đây không phải giả thuyết: nó đã từng gây ra các lỗ hổng denial-of-service thật trước khi các implementation chuyển sang pivot ngẫu nhiên.

Các chiến lược chọn pivot, theo thứ tự tăng dần độ vững chắc:

Chiến lược	Worst case bị kích hoạt bởi
Phần tử đầu/cuối	Input đã sắp hoặc sắp ngược — rất phổ biến
Phần tử giữa	Một input được dựng có chủ đích; an toàn với dữ liệu đã sắp
Median-of-three (đầu, giữa, cuối)	Một input “median-of-three killer” được dựng riêng
Pivot ngẫu nhiên	Không có gì kẻ tấn công dựng trước được — worst case có xác suất O(1/n!)
Median-of-medians	Không gì cả — bảo đảm O(n log n), nhưng hằng số nhân lớn tới mức không ai dùng thực tế

Hai điểm thực tế nữa:

• Phần tử trùng lặp. Phân hoạch hai chiều trên array toàn phần tử bằng nhau cho ra phân hoạch lệch tối đa: O(n²). Cách sửa là phân hoạch ba chiều (thuật toán Dutch National Flag): chia thành < pivot, == pivot, > pivot và chỉ đệ quy vào hai phần ngoài. Nhờ đó array có k giá trị phân biệt được sort trong O(n log k), và array toàn phần tử bằng nhau chỉ tốn O(n).
• Quickselect. Cũng bước phân hoạch đó, nhưng chỉ đệ quy vào một bên, tìm được phần tử nhỏ thứ k trong thời gian kỳ vọng O(n) mà không cần sort toàn bộ — xem ./20-brute-force-greedy-and-randomised-algorithms.md.

Dù worst case tệ hơn, quicksort thường nhanh hơn merge sort về thời gian thực tế: nó in-place (không cấp phát, không tải bộ nhớ thêm), vòng lặp trong là một lần quét tuần tự chặt chẽ mà cache và branch predictor rất thích, và hằng số nhân của nó chỉ khoảng một nửa merge sort.

Heap sort

Dựng một max-heap ngay trên array, rồi liên tục hoán đổi root (phần tử lớn nhất) với phần tử cuối của heap và thu nhỏ heap đi một, khôi phục tính chất heap sau mỗi lần. Array dần hình thành một đuôi đã sắp xếp từ bên phải.

def _sift_down(arr, start, end):
    """Khôi phục tính chất max-heap tại chỉ số `start` trong phạm vi arr[0:end]."""
    root = start
    while True:
        child = 2 * root + 1               # con trái theo layout array
        if child >= end:
            return
        if child + 1 < end and arr[child] < arr[child + 1]:
            child += 1                     # lấy con lớn hơn trong hai con
        if arr[root] >= arr[child]:
            return                         # tính chất heap đã thỏa
        arr[root], arr[child] = arr[child], arr[root]
        root = child


def heap_sort(arr):
    n = len(arr)
    # Giai đoạn 1: heapify từ dưới lên. Đây là O(n), KHÔNG phải O(n log n) — phần
    # lớn node nằm gần lá và chỉ phải sift down một hai tầng.
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(arr, start, n)
    # Giai đoạn 2: liên tục rút phần tử lớn nhất vào phần đuôi đã sắp.
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # max về đúng vị trí cuối cùng
        _sift_down(arr, 0, end)               # khôi phục heap trên phần tiền tố
    return arr

Độ phức tạp: O(n log n) trong mọi trường hợp — dựng heap tốn O(n), sau đó n lần rút, mỗi lần O(log n). Bộ nhớ O(1), in-place thật sự. Không stable.

Heap sort là thuật toán duy nhất ở đây vừa có bảo đảm O(n log n) vừa dùng O(1) bộ nhớ. Vậy mà nó hiếm khi nhanh nhất: nó truy cập bộ nhớ theo kiểu nhảy cóc (index i → 2i+1), rất bất lợi cho cache, và nó thực hiện khoảng gấp đôi số phép so sánh của quicksort. Vai trò production thật sự của nó là làm phương án dự phòng trong introsort — tốc độ của quicksort cộng bảo đảm của heap sort, đúng là đánh đổi mà std::sort của C++ chọn.

Khái niệm chính

Cận dưới Ω(n log n) cho comparison sort

Bất kỳ thuật toán nào chỉ tìm hiểu về input thông qua việc so sánh từng cặp phần tử đều có thể mô hình hóa bằng một cây quyết định (decision tree): mỗi node trong là một phép so sánh, mỗi nhánh là một kết quả, mỗi lá là một hoán vị mà thuật toán có thể xuất ra.

                        a₁ : a₂
                    ≤ /         \ >
              a₂ : a₃             a₁ : a₃
             /       \           /       \
       ⟨1,2,3⟩    a₁ : a₃   ⟨2,1,3⟩    a₂ : a₃
                  /     \               /     \
            ⟨1,3,2⟩  ⟨3,1,2⟩      ⟨2,3,1⟩  ⟨3,2,1⟩

Lập luận gồm ba dòng:

1. Để sort đúng, cây phải có ít nhất n! lá — mỗi hoán vị input một lá, vì thuật toán phải có khả năng tạo ra bất kỳ hoán vị nào.
2. Cây nhị phân có L lá thì chiều cao ít nhất là log₂ L. Số phép so sánh trong worst case chính là chiều cao.
3. log₂(n!) = Θ(n log n) theo xấp xỉ Stirling (n! ≈ (n/e)ⁿ√(2πn), nên log₂(n!) ≥ n log₂ n − n log₂ e).

Do đó mọi comparison sort đều cần Ω(n log n) phép so sánh trong worst case. Merge sort và heap sort đạt đúng cận này nên tối ưu về mặt tiệm cận. Không có comparison sort thông minh nào đang chờ được khám phá — cận này là một định lý, không phải một phỏng đoán.

Hãy chú ý chính xác nó ràng buộc điều gì: số phép so sánh, trong worst case. Nó không nói gì về các thuật toán nhìn vào chính nội dung của phần tử.

Non-comparison sort: cách né cận dưới

Nếu bạn có thể nhìn vào bên trong key — đọc từng chữ số của nó, dùng nó làm index của array — thì bạn đã ở ngoài mô hình decision tree và cận dưới không áp dụng nữa.

Counting sort

Dành cho key là số nguyên trong một khoảng nhỏ đã biết [0, k]: đếm số lần xuất hiện của mỗi giá trị, tính prefix sum để có vị trí bắt đầu, rồi đặt trực tiếp từng phần tử.

def counting_sort(arr, k):
    """Counting sort stable cho số nguyên trong [0, k]. Thời gian và bộ nhớ O(n + k)."""
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1
    # Prefix sum biến "có bao nhiêu phần tử bằng v" thành "chỉ số ngay sau ô cuối của v"
    for v in range(1, k + 1):
        counts[v] += counts[v - 1]
    out = [None] * len(arr)
    for x in reversed(arr):            # duyệt ngược để giữ tính stable
        counts[x] -= 1
        out[counts[x]] = x
    return out


assert counting_sort([4, 2, 2, 8, 3, 3, 1], 8) == [1, 2, 2, 3, 3, 4, 8]

Thời gian và bộ nhớ O(n + k). Tuyến tính khi k = O(n), và vô dụng khi k khổng lồ — counting-sort 1000 số nguyên 64-bit ngẫu nhiên sẽ cấp phát một array 2⁶⁴ bộ đếm. Tính stable quan trọng ở đây vì counting sort là vòng lặp trong của radix sort.

Radix sort

Sort lần lượt theo từng vị trí chữ số, bắt đầu từ chữ số ít quan trọng nhất (LSD), dùng một sort stable cho mỗi chữ số. Tính stable không phải thứ có cũng được: nó chính là thứ bảo toàn thứ tự đã được thiết lập bởi các chữ số ít quan trọng hơn ở lượt trước.

input     lượt 1 (đơn vị)  lượt 2 (chục)   lượt 3 (trăm)
 170        170              802             002
  45        090              002             045
  75        802              024             066
  90        024              045             075
 802        045              075             090
  24        075              170             170
   2        066              090             802
  66        002              066             ...

def radix_sort(arr, base=10):
    """LSD radix sort cho số nguyên không âm. Thời gian O(d * (n + base)),
    với d là số chữ số của giá trị lớn nhất."""
    if not arr:
        return []
    out = list(arr)
    max_val = max(out)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(base)]
        for x in out:
            buckets[(x // exp) % base].append(x)   # stable: append theo đúng thứ tự
        out = [x for bucket in buckets for x in bucket]
        exp *= base
    return out


assert radix_sort([170, 45, 75, 90, 802, 24, 2, 66]) == [2, 24, 45, 66, 75, 90, 170, 802]

O(d·(n + b)) với d là số chữ số và b là cơ số. Với key có độ rộng cố định (số nguyên 32-bit, b = 256, d = 4) thì đó là O(n) — tuyến tính thật sự. Implementation thực tế dùng cơ số 256 và phép dịch bit, chứ không dùng cơ số 10 và phép chia. Radix sort là thứ mà các database engine và hệ thống phân tích dạng cột dùng cho các cột số nguyên, và nó thắng thoải mái các sort O(n log n) trên array số nguyên lớn.

Bucket sort

Rải phần tử vào n bucket theo giá trị, sort từng bucket, rồi nối lại. Hoạt động tốt khi input phân bố xấp xỉ đều trên một khoảng đã biết.

def bucket_sort(arr, n_buckets=None):
    """Bucket sort cho số thực phân bố đều trong [0, 1).
    Kỳ vọng O(n), worst case O(n^2) (mọi phần tử rơi vào một bucket)."""
    if not arr:
        return []
    n = n_buckets or len(arr)
    buckets = [[] for _ in range(n)]
    for x in arr:
        buckets[min(int(x * n), n - 1)].append(x)
    out = []
    for bucket in buckets:
        out.extend(insertion_sort(bucket))   # kỳ vọng mỗi bucket chỉ chứa ~1 phần tử
    return out

O(n) kỳ vọng — và kỳ vọng đó phụ thuộc hoàn toàn vào phân bố dữ liệu. Đưa vào dữ liệu lệch thì mọi thứ rơi vào một bucket, và bạn nhận về O(n²) của sort bên trong. Bucket sort là thuật toán bạn chọn khi biết chắc điều gì đó cụ thể về dữ liệu (số đo cảm biến phân bố đều, giá trị hash, điểm số đã chuẩn hóa), còn ngoài ra thì không.

Bảng so sánh đầy đủ

Thuật toán	Best	Trung bình	Worst	Bộ nhớ	Stable	In-place	Ghi chú
Bubble sort	O(n)¹	O(n²)	O(n²)	O(1)	Có	Có	Nhiều lần hoán đổi nhất; chỉ để dạy học
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	Không	Có	Đúng n−1 lần hoán đổi — số lần ghi tối thiểu
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Có	Có	Adaptive, online; base case của các sort thật
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Có	Không	Bảo đảm chặt; dùng cho linked list & external sort
Quicksort	O(n log n)	O(n log n)	O(n²)²	O(log n)	Không	Có	Nhanh nhất thực tế; cần chọn pivot tốt
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	Không	Có	Vừa bảo đảm vừa in-place; bất lợi cho cache
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	Có	Không	Mặc định của Python/Java; tận dụng run có sẵn
Counting sort	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Có	Không	Chỉ với khoảng số nguyên nhỏ
Radix sort (LSD)	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	Có	Không	Key độ rộng cố định; tuyến tính trong thực tế
Bucket sort	O(n + k)	O(n + k)	O(n²)	O(n)	Có³	Không	Đòi hỏi phân bố đều

¹ Khi có cờ swapped thoát sớm; không có nó thì là O(n²). ² O(n log n) với xác suất rất cao nếu pivot ngẫu nhiên; O(n log n) bảo đảm nếu có phương án dự phòng heap sort của introsort. ³ Stable nếu sort bên trong mỗi bucket là stable.

Các thư viện chuẩn thực tế dùng gì

Không ai đem một thuật toán sách giáo khoa lên production. Mọi sort production đều là một hybrid, và đọc chúng là bản tóm tắt tốt nhất cho mọi thứ ở trên.

Timsort — list.sort() / sorted() của Python, Arrays.sort cho object của Java

Do Tim Peters phát minh cho CPython năm 2002 dựa trên nhận xét rằng dữ liệu thật hiếm khi ngẫu nhiên — nó thường đã sắp một phần, được nối từ các đoạn đã sắp, hoặc đã được sort theo một key khác.

1. Quét array tìm các run tự nhiên — các đoạn tăng dần hoặc giảm dần nghiêm ngặt dài nhất (đoạn giảm được đảo ngược tại chỗ, cách này giữ được tính stable).
2. Run ngắn hơn minrun (32–64, tính từ n) được kéo dài tới minrun bằng binary insertion sort.
3. Các run được đẩy vào một stack và merge theo các bất biến giữ cho độ dài các run cân bằng, nhờ đó các lần merge tổng cộng là O(n log n).
4. Galloping mode: khi một run liên tục thắng trong quá trình merge, chuyển từ bước nhảy tuyến tính sang tìm kiếm mũ để bỏ qua các phần tử của nó trong O(log n) thay vì O(k).

Kết quả: O(n) với input đã sắp hoặc sắp ngược, O(n log n) worst case, stable, và nhanh hơn merge sort thuần rất nhiều trên dữ liệu thực tế. Tính stable của sort trong Python là bảo đảm ở mức ngôn ngữ đã được ghi trong tài liệu, không phải chi tiết implementation — bạn có thể dựa vào nó.

Introsort — std::sort của C++

Là quicksort, nhưng có gắn thiết bị đo:

• Bắt đầu bằng quicksort với pivot median-of-three.
• Nếu độ sâu đệ quy vượt 2·log₂ n, rõ ràng pivot đang bệnh lý — chuyển sang heap sort cho subarray đó, chặn worst case ở O(n log n).
• Dưới khoảng 16 phần tử, ngừng đệ quy và kết thúc bằng một lượt insertion sort duy nhất trên toàn bộ array đã gần sắp xếp.

Bạn nhận được tốc độ trung bình của quicksort cùng bảo đảm worst case của heap sort. std::sort không stable; std::stable_sort là một hàm riêng (một merge sort adaptive) chính vì tính stable phải trả giá bằng bộ nhớ.

pdqsort — sort_unstable của Rust, sort/slices.Sort của Go 1.19+

“Pattern-defeating quicksort” mở rộng introsort:

• Phát hiện các mẫu đã sắp và sắp ngược rồi rút ngắn chúng về O(n).
• Dùng phân hoạch branchless, tránh các lần dự đoán nhánh sai vốn chiếm phần lớn chi phí của quicksort trên dữ liệu ngẫu nhiên — một cải thiện thực tế rất lớn chẳng liên quan gì tới tiệm cận.
• Chuyển sang heap sort với các mẫu xấu, và ngẫu nhiên hóa pivot khi phát hiện input mang tính đối kháng.

Cách đặt tên của Rust rất thành thật về đánh đổi: sort() stable và có cấp phát; sort_unstable() là pdqsort, in-place, và nhanh hơn. Go chuyển sort chuẩn từ một biến thể introsort sang pdqsort ở phiên bản 1.19 vì cùng những lý do đó.

Sắp xếp trong Python, một cách thực dụng

from operator import itemgetter, attrgetter

people = [("Chi", 40), ("Anh", 31), ("Binh", 31)]

# `sorted` trả về list mới; `list.sort()` sort tại chỗ và trả về None.
by_age = sorted(people, key=itemgetter(1))          # O(n log n), stable
people.sort(key=itemgetter(1))                      # không copy, nhanh hơn một chút

# Sort theo nhiều key, cùng chiều tăng dần — dựng key dạng tuple
by_age_then_name = sorted(people, key=lambda p: (p[1], p[0]))

# Khác chiều nhau: dựa vào tính STABLE và sort theo key ít quan trọng nhất
# trước. Đây chính là nguyên lý làm LSD radix sort hoạt động.
rows = sorted(people, key=itemgetter(0))            # phụ: tên tăng dần
rows = sorted(rows, key=itemgetter(1), reverse=True) # chính: tuổi giảm dần

# Hàm key được gọi đúng một lần cho mỗi phần tử (decorate-sort-undecorate),
# nên key tốn kém vẫn chấp nhận được. Comparator kiểu cmp thì KHÔNG:
# functools.cmp_to_key bị gọi O(n log n) lần và chậm hơn hẳn — chỉ dùng khi thứ
# tự thật sự không thể biểu diễn bằng một key.

Hai thói quen quan trọng hơn cả việc chọn thuật toán:

• Bạn không cần sort toàn bộ để lấy k phần tử lớn nhất. heapq.nlargest(k, data) là O(n log k), và với k nhỏ thì tốt hơn nhiều so với sorted(data)[-k:] ở O(n log n).
• Bạn không cần sort để lấy trung vị. Quickselect kỳ vọng O(n); statistics.median trên list lớn là O(n log n) vì nó sort.

Best Practices

• Dùng hàm sort có sẵn của ngôn ngữ. Nó là một hybrid được tinh chỉnh qua hàng chục năm, nó stable đúng như nó tuyên bố, và quicksort tự viết của bạn sẽ vừa chậm hơn vừa nhiều bug hơn. Cài đặt sort để học, không phải để ship.
• Biết rõ sort của bạn có stable hay không, đừng bao giờ đoán. sorted/list.sort của Python và sort cho object của Java là stable. std::sort của C++, sort_unstable của Rust, Arrays.sort cho kiểu nguyên thủy của Java, và mọi quicksort trần đều không. Sort theo nhiều key sẽ âm thầm cho ra kết quả sai trên một sort không stable.
• Sort bằng key, không bằng comparator. key= được gọi một lần mỗi phần tử; comparator bị gọi O(n log n) lần. functools.cmp_to_key là lối thoát hiểm, không phải mặc định.
• Đừng bao giờ viết quicksort trần với pivot là phần tử đầu tiên. Input đã sắp là worst case, và input đã sắp thì rất phổ biến. Hãy ngẫu nhiên hóa pivot hoặc dùng median-of-three cộng giới hạn độ sâu có phương án dự phòng.
• Dùng phân hoạch ba chiều khi khả năng có nhiều phần tử trùng lặp. Mã trạng thái, category, boolean, timestamp làm tròn theo ngày — quicksort hai chiều suy biến thành O(n²) với những dữ liệu này; ba chiều xử lý chúng trong O(n log k).
• Chọn non-comparison sort khi key cho phép. Số nguyên khoảng nhỏ, ID độ rộng cố định, ngày tháng, và chuỗi byte đều có thể counting- hoặc radix-sort trong thời gian tuyến tính. Đây là cải thiện thật và lớn trên array lớn, không phải micro-optimization — nhưng hãy kiểm tra khoảng giá trị của key trước, vì counting sort trên khoảng rộng sẽ cấp phát bộ nhớ tới mức thảm họa.
• Tự hỏi liệu bạn có thật sự cần sort toàn bộ không. Top-k cần một heap (./12-heaps-and-priority-queues.md); trung vị hay phần tử thứ k cần quickselect; kiểm tra thành viên cần hash table (./07-hash-tables.md); “có phần tử nào trùng không” cần một set. Sort để trả lời những câu này là làm việc O(n log n) cho một câu hỏi O(n).
• Đẩy việc sort xuống database khi dữ liệu nằm ở đó. Một index vốn đã lưu row theo đúng thứ tự cần thiết biến ORDER BY thành một lần quét không cần sort chút nào — xem ../../postgresql-dba/vi/10-query-planning-and-performance-tuning.md và ./18-indexing.md.
• Sort một lần, truy vấn nhiều lần. Nếu bạn sẽ tìm kiếm trên một tập dữ liệu nhiều lần, hãy trả O(n log n) một lần rồi binary search ở O(log n), thay vì quét tuyến tính mỗi lần (./09-search-algorithms.md).
• Cẩn thận với O(n²) ẩn trong hàm so sánh. Một key hay comparator tự nó làm việc tuyến tính (nối chuỗi, truy vấn database, tính lại một field dẫn xuất) sẽ khiến cả lần sort trở thành bậc hai. Hãy tính trước key.
• Với dữ liệu lớn hơn bộ nhớ, hãy nghĩ tới merge sort. Sort từng chunk vừa RAM, ghi ra đĩa, rồi k-way merge bằng một heap. Đây là cách sort(1), external sort của database, và shuffle của Spark đều làm.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Sorting algorithm — Wikipedia
• Comparison sort — Wikipedia (the Ω(n log n) lower bound)
• CLRS — Introduction to Algorithms, Chapters 2, 6, 7, 8
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Timsort — Wikipedia
• CPython source — Objects/listsort.txt (Tim Peters’ description of Timsort)
• Introsort — Wikipedia
• pdqsort — pattern-defeating quicksort (reference implementation)
• Dutch national flag problem — Wikipedia
• Radix sort — Wikipedia
• Python Documentation — Sorting Techniques (HOWTO)
• Big-O Cheat Sheet
• VisuAlgo — Sorting

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        # After pass i, the last i elements are already in their final place,
        # so the inner loop can shrink.
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:        # nothing moved: the array is sorted — O(n) best case
            break
    return arr

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):        # scan the unsorted suffix for its minimum
            if arr[j] < arr[m]:
                m = j
        arr[i], arr[m] = arr[m], arr[i]  # exactly one swap per pass
    return arr

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Shift everything strictly greater than `key` one slot to the right.
        # Strict `>` (not `>=`) leaves equal elements in their original order,
        # which is exactly what makes insertion sort stable.
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

                 [38, 27, 43, 3, 9, 82, 10]
                 /                        \
        [38, 27, 43]                  [3, 9, 82, 10]
        /          \                  /            \
    [38]      [27, 43]           [3, 9]        [82, 10]
              /     \            /    \         /    \
           [27]     [43]      [3]     [9]    [82]    [10]
              \     /            \    /         \    /
              [27, 43]           [3, 9]        [10, 82]
        \          /                  \            /
        [27, 38, 43]                  [3, 9, 10, 82]
                 \                        /
                 [3, 9, 10, 27, 38, 43, 82]

def merge_sort(arr):
    if len(arr) <= 1:                  # base case: 0 or 1 element is sorted
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def _merge(left, right):
    """Merge two sorted lists into one sorted list. O(len(left) + len(right))."""
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        # `<=` rather than `<` is what makes merge sort stable: on a tie, the
        # element from the left half — the one that came first — is taken first.
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])               # one of these is empty
    out.extend(right[j:])
    return out

import random


def quick_sort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    while lo < hi:
        p = _partition(arr, lo, hi)
        # Recurse into the smaller side and loop on the larger one. This keeps
        # the recursion depth at O(log n) even when the splits are bad.
        if p - lo < hi - p:
            quick_sort(arr, lo, p - 1)
            lo = p + 1
        else:
            quick_sort(arr, p + 1, hi)
            hi = p - 1
    return arr


def _partition(arr, lo, hi):
    """Lomuto partition with a randomly chosen pivot.
    Returns the index where the pivot ended up — its final sorted position."""
    r = random.randint(lo, hi)
    arr[r], arr[hi] = arr[hi], arr[r]      # park the pivot at the end
    pivot = arr[hi]
    i = lo                                 # invariant: arr[lo:i] < pivot
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]      # pivot into its final place
    return i

def _sift_down(arr, start, end):
    """Restore the max-heap property at index `start` within arr[0:end]."""
    root = start
    while True:
        child = 2 * root + 1               # left child in the array layout
        if child >= end:
            return
        if child + 1 < end and arr[child] < arr[child + 1]:
            child += 1                     # take the larger of the two children
        if arr[root] >= arr[child]:
            return                         # heap property already holds
        arr[root], arr[child] = arr[child], arr[root]
        root = child


def heap_sort(arr):
    n = len(arr)
    # Phase 1: heapify bottom-up. This is O(n), NOT O(n log n) — most nodes are
    # near the leaves and sift down only a level or two.
    for start in range(n // 2 - 1, -1, -1):
        _sift_down(arr, start, n)
    # Phase 2: repeatedly extract the max into the growing sorted suffix.
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]   # max goes to its final position
        _sift_down(arr, 0, end)               # restore the heap on the prefix
    return arr

                        a₁ : a₂
                    ≤ /         \ >
              a₂ : a₃             a₁ : a₃
             /       \           /       \
       ⟨1,2,3⟩    a₁ : a₃   ⟨2,1,3⟩    a₂ : a₃
                  /     \               /     \
            ⟨1,3,2⟩  ⟨3,1,2⟩      ⟨2,3,1⟩  ⟨3,2,1⟩

def counting_sort(arr, k):
    """Stable counting sort of integers in [0, k]. O(n + k) time, O(n + k) space."""
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1
    # Prefix sums turn "how many equal v" into "index just past the last slot for v"
    for v in range(1, k + 1):
        counts[v] += counts[v - 1]
    out = [None] * len(arr)
    for x in reversed(arr):            # iterate backwards to preserve stability
        counts[x] -= 1
        out[counts[x]] = x
    return out


assert counting_sort([4, 2, 2, 8, 3, 3, 1], 8) == [1, 2, 2, 3, 3, 4, 8]

input     pass 1 (units)   pass 2 (tens)   pass 3 (hundreds)
 170        170              802             002
  45        090              002             045
  75        802              024             066
  90        024              045             075
 802        045              075             090
  24        075              170             170
   2        066              090             802
  66        002              066             ...

def radix_sort(arr, base=10):
    """LSD radix sort of non-negative integers. O(d * (n + base)) time,
    where d is the number of digits in the largest value."""
    if not arr:
        return []
    out = list(arr)
    max_val = max(out)
    exp = 1
    while max_val // exp > 0:
        buckets = [[] for _ in range(base)]
        for x in out:
            buckets[(x // exp) % base].append(x)   # stable: appended in order
        out = [x for bucket in buckets for x in bucket]
        exp *= base
    return out


assert radix_sort([170, 45, 75, 90, 802, 24, 2, 66]) == [2, 24, 45, 66, 75, 90, 170, 802]

def bucket_sort(arr, n_buckets=None):
    """Bucket sort for floats uniformly distributed in [0, 1).
    O(n) expected, O(n^2) worst case (everything in one bucket)."""
    if not arr:
        return []
    n = n_buckets or len(arr)
    buckets = [[] for _ in range(n)]
    for x in arr:
        buckets[min(int(x * n), n - 1)].append(x)
    out = []
    for bucket in buckets:
        out.extend(insertion_sort(bucket))   # buckets are expected to hold ~1 element
    return out

from operator import itemgetter, attrgetter

people = [("Chi", 40), ("Anh", 31), ("Binh", 31)]

# `sorted` returns a new list; `list.sort()` sorts in place and returns None.
by_age = sorted(people, key=itemgetter(1))          # O(n log n), stable
people.sort(key=itemgetter(1))                      # no copy, slightly faster

# Multi-key sort, ascending on both — build a tuple key
by_age_then_name = sorted(people, key=lambda p: (p[1], p[0]))

# Mixed directions: rely on STABILITY and sort by the least significant key
# first. This is the same principle that makes LSD radix sort work.
rows = sorted(people, key=itemgetter(0))            # secondary: name ascending
rows = sorted(rows, key=itemgetter(1), reverse=True) # primary: age descending

# The key function is called exactly once per element (decorate-sort-undecorate),
# so an expensive key is fine. A cmp-style comparator is NOT: functools.cmp_to_key
# is called O(n log n) times and is markedly slower — use it only when the order
# genuinely cannot be expressed as a key.