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.
Phân trang OFFSET 0 quét 20 hàng (0,02ms), nhưng OFFSET 500000 quét 500020 hàng (34ms) và trang cuối quét cả triệu hàng (64ms). Chi phí tăng tuyến tính theo độ sâu — và tôi suýt bỏ qua vì chỉ thử trang đầu. Keyset pagination nhảy thẳng qua index, nhanh đều 0,03ms mọi trang. Vì sao OFFSET đếm còn keyset tra cứu.
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.
Bài mảng con tổng lớn nhất có lời giải chia để trị đẹp như sách giáo khoa, O(n log n). Nhưng đo ra Kadane — một vòng quét O(n) tầm thường — nhanh hơn 20 lần (5,3 so 112 ms ở 10 triệu phần tử) và gọn hơn hẳn. Chia để trị mạnh và tổng quát, nhưng đẹp không đồng nghĩa tối ưu. 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.