Heapsort nghe như hoàn hảo: O(n log n) bảo đảm và tại chỗ — hơn quicksort có ca xấu, hơn merge tốn bộ nhớ. Nhưng đo ra nó chậm nhất trong ba (1,43× tới 2,37× quicksort), và tỉ số tăng theo n vì sift-down nhảy khắp mảng phá cache. Vai trò thật của nó là lưới an toàn, không phải tốc độ. Tôi đo.
O(n²) nghe như luôn thua O(n log n), nhưng đo ra sai hai lần: ở mảng nhỏ (tới ~128 phần tử) insertion sort nhanh hơn quicksort, và trên mảng đã sắp nó chỉ O(n) — 0,09 ms so với quicksort 1,7 ms, nhanh hơn 19 lần. Big-O là ca xấu nhất tiệm cận; n nhỏ và dữ liệu có sẵn thứ tự thì khác hẳn. Tôi đo.
Không thuật toán sắp xếp đơn nào thắng mọi mặt, nên std::sort của C++ ghép quicksort + insertion + heapsort, mỗi cái che điểm yếu cái kia. Ngưỡng insertion chỉ đáng ~14% chứ không nhiều; và cùng mảng đã sắp giết quicksort pivot cuối (331 ms, đệ quy 50000 tầng) thì introsort xong trong 0,27 ms. 'Tốt nhất' là một kiến trúc, không phải một cái tên. Tôi đo.
Mọi sắp xếp dựa trên so sánh bị chặn ở O(n log n). Nhưng radix và counting sort chạy O(n): radix thắng introsort 5–11 lần trên số 32-bit ở mọi cỡ, counting sort nhanh 15,6 lần với khóa nhỏ. Giới hạn thật không ở n nhỏ mà ở bề rộng khóa (32-bit 4 lượt, 64-bit 8 lượt) và scatter phá cache. Tôi đo.
Tưởng độ sâu đệ quy tùy ý, nhưng ngăn xếp OS chỉ 8 MB, mỗi khung ~13 byte, nên có trần cứng ~655.000 lần gọi rồi segfault không một lời cảnh báo. Và bất ngờ: đệ quy KHÔNG chậm hơn vòng lặp (22,8 so 22,7 µs) — cái đắt của nó là trần ngăn xếp, không phải tốc độ. Cách chữa: ngăn xếp tường minh trên heap. Tôi đo.
Fibonacci đệ quy khớp y hệt định nghĩa toán học, nhưng đo ra nó nổ theo hàm mũ: fib(43) gọi 1,4 tỉ lần, mất 447 ms, vì tính lại bài con chồng lấn. Quy hoạch động chỉ là 'nhớ để khỏi tính lại': memo đưa về 85 lời gọi, dưới 1 micro giây. Tabulation nhanh hơn memo 28 lần và không tràn ngăn xếp. Tôi đo.