Đếm số so sánh thì B-tree thua tìm nhị phân (bậc 64 làm 100 so với 20). Đo thời gian thì thắng (70 ns so với 98 ns) vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật. Và có bậc B tối ưu quanh cỡ dòng cache, không phải càng lớn càng nhanh. Tôi đo.
Chèn từng phần tử để dựng heap 'phải là' O(n log n). Nhưng đo dữ liệu ngẫu nhiên thì nó phẳng 2,3 thao tác/phần tử — cũng O(n). O(n log n) chỉ hiện ở ca xấu (chèn giảm dần): thao tác leo 16→22 theo log n. Heapify thì O(n) bất kể đầu vào. Và heap không sắp xếp — nó chỉ cho min rẻ. Tôi đo.
Quicksort là O(n log n) — nên nhiều người vô tư lấy pivot phần tử cuối. Nhưng trên mảng đã sắp (rất thường gặp) nó thành O(n²): thời gian gấp 4 mỗi khi n gấp đôi, ~3000 lần chậm hơn ở 1 triệu, và đệ quy sâu n tầng tràn ngăn xếp. Trung vị-của-3 cứu: về 9 ms. Tôi đo.
Merge sort cùng O(n log n) với quicksort nhưng đo ra chậm hơn 1,25 lần. Tôi đổ lỗi cho malloc trong bước trộn — đo lại thì malloc chỉ chiếm +6%, thủ phạm thật là chép dữ liệu qua đệm (+23 ms). Giá trị thật của merge không phải tốc độ mà là ổn định (0 vs 488.887 cặp đảo) và không có ca xấu. Tôi đo.
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.