Sắp xếp là thao tác cơ bản đến mức ai cũng gõ std::sort (hay sorted(), Arrays.sort()) mà không nghĩ. Nhưng các thuật toán sắp xếp chia thành hai họ theo bộ nhớ phụ chúng cần, và lựa chọn giữa hai họ đó đổi cả bộ nhớ lẫn một tính chất quan trọng ít ai để ý: tính ổn định. Tôi đo std::sort (tại chỗ) so với std::stable_sort (cấp thêm) trên 20 triệu phần tử trong container gcc:13, cộng một quicksort tự cài để cho thấy cái bẫy worst case — và con số cho thấy "sắp xếp nào cũng như nhau" giấu ba đánh đổi thật.
Hai họ: đổi bộ nhớ lấy tính ổn định
Sắp xếp tại chỗ (in-place): sắp ngay trên mảng, chỉ tốn O(1)–O(log n) bộ nhớ thêm (stack đệ quy). std::sort dùng introsort — quicksort là chính, chuyển sang heapsort khi đệ quy quá sâu, và insertion sort cho đoạn nhỏ. Ít RAM. Nhưng thường không ổn định: nếu hai phần tử bằng nhau (theo khóa so sánh), thứ tự tương đối của chúng sau khi sắp có thể đổi.
Sắp xếp cấp thêm (out-of-place): merge sort cần một buffer O(n) để trộn hai nửa đã sắp. std::stable_sort dùng cách này. Tốn n phần tử bộ nhớ thêm, nhưng ổn định (giữ nguyên thứ tự phần tử bằng nhau) và mẫu truy cập tuần tự — thân thiện cache.
Tính ổn định nghe nhỏ nhưng quan trọng thật: khi bạn sắp một danh sách theo nhiều tiêu chí (sắp theo tên rồi sắp theo tuổi), tính ổn định giữ thứ tự tên trong nhóm cùng tuổi. Không ổn định thì bạn mất kết quả sắp trước.
Đo: 80 MB buffer, và một cái bẫy O(n²)
Tôi sắp 20 triệu số nguyên ngẫu nhiên bằng cả hai cách:
N = 20 triệu int, g++ -O2:
A. BỘ NHỚ PHỤ:
tại chỗ (std::sort, introsort) : ~0 buffer (O(log n) stack)
cấp thêm (std::stable_sort, merge) : 80 MB buffer (O(n) = N × 4 byte)
B. TỐC ĐỘ (dữ liệu ngẫu nhiên):
std::sort (tại chỗ) : 47,9 ns/phần tử | 0 buffer
std::stable_sort (cấp thêm) : 58,0 ns/phần tử | 80 MB buffer, ỔN ĐỊNH
C. QUICKSORT pivot XẤU (phần tử cuối) trên dữ liệu ĐÃ SẮP XẾP:
M = 100.000 : 14.851 ns/phần tử (O(n²)!)
std::sort cùng dữ liệu : 6,1 ns/phần tử
-> quicksort pivot xấu chậm ~2428 lần (worst case)
Nhìn A: std::stable_sort cần một buffer 80 MB (20 triệu int × 4 byte) để trộn, còn std::sort gần như không tốn gì thêm. Với dữ liệu rất lớn hoặc bộ nhớ eo hẹp, 80 MB đó có thể là vấn đề. B: trên dữ liệu ngẫu nhiên, std::sort vừa nhanh hơn (47,9 so với 58,0 ns/phần tử) vừa tốn ít RAM hơn — nhưng std::stable_sort cho tính ổn định, thứ mà std::sort không đảm bảo. Đây là đánh đổi thật: cần ổn định thì trả bằng 80 MB và ~20% thời gian.
C là cái bẫy kinh điển của quicksort tự cài: nếu bạn chọn pivot cố định (ví dụ luôn lấy phần tử cuối) và dữ liệu đã sắp xếp, mọi lần phân hoạch đều lệch hết về một phía — đúng như cây tìm kiếm suy biến ở phần 7 — biến quicksort thành O(n²). Đo cho thấy nó chậm ~2428 lần std::sort trên cùng dữ liệu. std::sort (introsort) tránh được vì nó phát hiện khi đệ quy quá sâu và chuyển sang heapsort (O(n log n) đảm bảo). Đây là lý do bạn nên dùng thư viện chuẩn, không tự cài quicksort ngây thơ.
Một lần tôi đo hớ: "sắp xếp nào cũng như nhau" và "in-place luôn tốt"
Tôi vào đo với niềm tin lười: "sắp xếp thì cứ std::sort, cái nào cũng như nhau". Đo cho thấy có đánh đổi thật: std::sort (tại chỗ) không tốn buffer nhưng không ổn định; std::stable_sort (cấp thêm) tốn 80 MB nhưng ổn định. Nếu bạn cần giữ thứ tự phần tử bằng nhau (sắp nhiều tiêu chí), std::sort cho kết quả sai theo nghĩa đó — phải stable_sort, và trả bằng bộ nhớ. Còn niềm tin ngược "in-place luôn tốt vì ít RAM" cũng thiếu: bạn mất tính ổn định, và nếu tự cài quicksort với pivot xấu, bạn có thể rơi vào O(n²) — 2428 lần chậm — mà thư viện chuẩn đã tránh giùm.
Bài học đo lường: sắp xếp TẠI CHỖ (std::sort introsort, ~0 buffer, 47,9 ns/pt) và CẤP THÊM (std::stable_sort merge, 80 MB buffer O(n), 58 ns/pt) khác về bộ nhớ phụ VÀ tính ỔN ĐỊNH — cần giữ thứ tự phần tử bằng nhau thì phải stable_sort, trả bằng n bộ nhớ; và quicksort tự cài với pivot XẤU trên dữ liệu đã sắp xếp thành O(n²) (đo 2428x chậm, như BST lệch phần 7), std::sort introsort tránh được worst case. Nếu tôi tin "cái nào cũng như nhau" tôi có thể dùng sắp không ổn định cho bài cần ổn định (kết quả sai) hoặc tốn 80 MB không cần; nếu tôi tin "in-place luôn tốt" và tự cài quicksort, tôi có thể tạo ra một O(n²) ẩn.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: dùng std::sort (hay tương đương) mặc định; dùng stable_sort khi cần tính ổn định. Nếu bạn chỉ sắp theo một khóa và không quan tâm thứ tự phần tử bằng nhau — std::sort, nhanh và ít RAM. Nếu bạn sắp nhiều tiêu chí (sắp lần lượt) hoặc cần giữ thứ tự gốc của phần tử bằng nhau — std::stable_sort, chấp nhận buffer O(n). Biết mình cần gì trước khi chọn.
Hệ quả thứ hai: đừng tự cài quicksort ngây thơ cho production — dùng thư viện. Quicksort với pivot xấu là O(n²) trên dữ liệu bất lợi (đã sắp xếp, gần sắp xếp) — một trong những lỗi hiệu năng phổ biến của người tự cài. Thư viện chuẩn dùng introsort (chuyển heapsort khi cần) hoặc timsort (Java/Python — merge sort thích ứng, khai thác các đoạn đã sắp sẵn), đã xử lý mọi worst case. Nếu phải tự cài, ít nhất chọn pivot ngẫu nhiên hoặc median-of-three.
Hệ quả thứ ba là tinh thần đo lường: "sắp xếp" là một tập lựa chọn có đánh đổi — bộ nhớ, tính ổn định, worst case — không phải một nút bấm. Con số mang theo: sắp xếp tại chỗ (std::sort, ~0 bộ nhớ phụ, không ổn định, 47,9 ns/pt) vs cấp thêm (std::stable_sort merge, 80 MB buffer O(n), ổn định, 58 ns/pt) — cần ổn định (giữ thứ tự phần tử bằng nhau, sắp nhiều tiêu chí) thì phải stable_sort trả bằng RAM; quicksort tự cài pivot xấu trên dữ liệu đã sắp xếp = O(n²) (2428x chậm), std::sort introsort tránh worst case. Chọn theo cần ổn định + ngân sách RAM; đừng tự cài quicksort ngây thơ. Cái nút sort che giấu một bảng đánh đổi.
Thử ba mươi giây
Sắp một mảng lớn bằng cả std::sort và std::stable_sort, bấm giờ và ước lượng bộ nhớ: bản stable tốn thêm một buffer bằng cả mảng. Rồi làm một thí nghiệm về ổn định: tạo các cặp (khóa, thứ tự gốc) với nhiều khóa trùng, sắp theo khóa bằng cả hai, và kiểm xem thứ tự gốc trong mỗi nhóm khóa có được giữ không — stable_sort giữ, std::sort có thể xáo. Cuối cùng, tự viết một quicksort chọn pivot là phần tử cuối, và chạy nó trên một mảng đã sắp xếp tăng dần vài trăm nghìn phần tử — nó sẽ chậm khủng khiếp (O(n²)), trong khi std::sort trên cùng dữ liệu bay vèo. Ba mươi giây đó cho bạn thấy điều mà "cứ sort là xong" giấu đi: có nhiều thuật toán sắp xếp với những đánh đổi khác nhau về bộ nhớ, tính ổn định và độ bền trước dữ liệu xấu — và thư viện chuẩn đã chọn khéo giùm bạn, miễn là bạn đừng tự cài lại một cách ngây thơ.
