Lý do chính là Branch Prediction (Dự đoán nhánh) của CPU hiện đại.
Cơ chế Branch Prediction
CPU cố gắng đoán trước nhánh if/else nào sẽ được thực thi để nạp sẵn lệnh vào pipeline. Nếu đoán đúng → thực thi liên tục. Nếu sai → phải flush pipeline, penalty lớn.
Ví dụ minh họa
if (arr[i] > 50) {
// Operation B
} else {
// Operation A
}
Mảng đã sắp xếp (1, 2, 3... 100)
1..50: A A A A ... A (50 lần) 51..100: B B B B ... B (50 lần) → Dễ dự đoán: A lặp nhiều lần, rồi B lặp nhiều lần. CPU học được pattern.
Mảng chưa sắp xếp (5, 51, 6, 90, 4, 49, 60...)
A, B, A, B, A, A, B ... → Pattern ngẫu nhiên, CPU dự đoán sai liên tục → pipeline flush liên tục → chậm.
Kết luận
Sắp xếp mảng giúp branch prediction hoạt động hiệu quả, giảm thiểu pipeline flush. Đây là tối ưu hóa cấp phần cứng, không phụ thuộc thuật toán.
Lưu ý: Biên dịch hiện đại (GCC, Clang, MSVC) có thể tự động vector hóa hoặc tối ưu hóa nhánh nếu dùng __builtin_expect hoặc profile-guided optimization (PGO).