เพราะ Branch Prediction (การคาดการณ์分支) ใน CPU architecture
Branch predictor พยายามทายว่า conditional branch (if/else) จะถูกทำหรือไม่ เพื่อโหลด instruction ล่วงหน้า (pipeline)
ตัวอย่าง
if (arr[i] > 50) { do_B(); } else { do_A(); }
Sorted array: 1, 2, 3... 50, 51... 100
A, A, A, A... A, B, B, B... (pattern สม่ำเสมอ ง่ายต่อการคาดการณ์)
Branch predictor ทายถูกเกือบทุกครั้ง pipeline ทำงานเต็มที่
Unsorted array: 5, 51, 6, 90, 4, 49, 60...
A, B, A, B, A, A, B... (pattern สลับซับซ้อน ยากต่อการคาดการณ์)
Branch predictor ทายผิดบ่อย pipeline flush บ่อย → ช้าลงมาก
สรุป: Sorted data ทำให้ branch pattern เป็นไปได้มากขึ้น branch predictor ทำงานได้ดี → เร็วกว่า
