Tại sao xử lý mảng đã sắp xếp nhanh hơn mảng chưa sắp xếp trong C++?

Trong C++, xử lý mảng đã sắp xếp nhanh hơn do dự đoán nhánh (branch prediction). Trong kiến trúc máy tính, branch prediction dự đoán nhánh điều kiện (jump) trong luồng lệnh có khả năng được thực thi hay không.

Ví dụ:

if (arr[i] > 50) {
    // Operation B
} else {
    // Operation A
}

Chạy cho 100 phần tử:

Mảng đã sắp xếp:

1, 2, 3... 50, 51... 100
A, A, A... A, B, B...
Pipeline tải đúng nhánh liên tiếp.

Mảng chưa sắp xếp:

5, 51, 6, 90, 4, 49, 60...
A, B, A, B, A, A, B...
Branch prediction khó dự đoán đúng.