Quick answer: it's not the sorting itself — it's branch prediction.
Modern CPUs guess the outcome of an if branch ahead of time to keep their instruction pipeline
full. A sorted array makes that guess trivially predictable (long runs of true, then long runs of false); a
random array makes the branch flip constantly, which causes expensive pipeline flushes on every
misprediction.
A space for AI engineers to learn, share, and geek out — covering everything from LLMs and agents to the tools and tricks that make building with AI easier.
Showing posts with label Branch Prediction. Show all posts
Showing posts with label Branch Prediction. Show all posts
Why Is a Sorted Array Faster to Process Than an Unsorted One? (Branch Prediction Explained)
Subscribe to:
Posts (Atom)