Why Is a Sorted Array Faster to Process Than an Unsorted One? (Branch Prediction Explained)

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.

The code that surprises people

if (data[c] >= 128)
    sum += data[c];

Run over 32,768 random bytes, this loop takes roughly 6x longer than the identical loop run over the same data, sorted first — even though sorting itself costs extra time, and the arithmetic inside the loop never changes.

Why sorting helps so much

CPUs pipeline instructions, starting the next one before the current one finishes. When they hit a conditional branch, they speculatively execute down the predicted path. Get it right, and it's free; get it wrong, and the CPU has to discard that speculative work and restart — often 10-20 cycles lost per misprediction. In a sorted array, values are either mostly below 128 or mostly above it in long contiguous runs, so the branch predictor is right almost every time. In a random array, it's right about 50% of the time, close to a coin flip, which is the worst case for a predictor.

Removing the branch entirely

// Branchless version: no misprediction possible
int t = (data[c] - 128) >> 31;   // -1 if negative (data[c] < 128), else 0
sum += ~t & data[c];

Bit-twiddling tricks like this, or simply letting the compiler auto-vectorize the loop with SIMD instructions, sidestep the branch altogether so performance stops depending on the data's order at all.

FAQ

Does this affect languages other than C++?

Yes — it's a CPU-level effect, not a language feature. The same slowdown shows up in Java, C#, Python (though interpreter overhead often masks it), and any compiled language with a data-dependent branch in a hot loop.

Is sorting always worth it for performance?

No. Sorting is O(n log n) and this example only pays off because the same array is scanned 100,000 times in a loop. For a single pass, sorting first would almost always cost more than it saves.

Do modern compilers still show this effect?

With aggressive optimization flags, many modern compilers auto-vectorize this specific loop and remove the branch entirely, shrinking or eliminating the gap — but the underlying branch-prediction principle still applies to countless other real-world branchy loops.

---

This article explains and expands on the community answers to the Stack Overflow question “Why is processing a sorted array faster than processing an unsorted array?”, used under the CC BY-SA 4.0 license. Screenshot credit: Stack Exchange Inc.