AVL sửa cây tìm kiếm suy biến: cùng khóa đã sắp, chiều cao 40000 xuống 16, tra 32538 ns xuống 215 ns. Nhưng trên khóa ngẫu nhiên AVL hơn không đáng kể mà tốn 27906 phép xoay — cân bằng là bảo hiểm cho ca xấu, không phải quà miễn phí. Và cùng cây cân bằng, bố cục bộ nhớ làm tra chênh 6 lần. Tôi đo.
Đế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.