Why Sorted Arrays Can Be Faster in C++: Branch Prediction Explained

By the end of this page, you will understand why a sorted array can make a loop much faster even when the algorithm is logically doing the same work. The main reason is usually CPU branch prediction: when data is sorted, the if condition becomes highly predictable, so the processor can keep its pipeline full. You will also see the roles of cache, compiler optimizations, and branchless alternatives.

The core concept here is branch prediction.

When your code contains a condition like this:

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

the CPU must decide whether the branch will be taken or not taken. Modern processors do not simply wait for the result of every condition. They try to predict the outcome in advance so they can keep executing instructions without stalling.

Why this matters

Modern CPUs are deeply pipelined. That means they prepare and execute multiple instruction stages at once. If the CPU predicts a branch correctly, execution continues smoothly. If it predicts incorrectly, it must throw away speculative work and restart from the correct path. This is called a branch misprediction.

A branch misprediction is expensive compared with a simple integer comparison.

Why sorted data helps

If the array is random, the condition data[c] >= 128 is also roughly random:

• sometimes true
• sometimes false
• often alternating unpredictably

That makes the branch hard to predict.

If the array is sorted, the pattern becomes predictable:

• first many values are < 128
• then many values are >= 128

So instead of a random true/false pattern, the CPU sees a long run of false outcomes followed by a long run of true outcomes. That is much easier to predict.

Important point

The improvement is usually not because sorting puts the data in cache. The array was already accessed during initialization, and the loop scans it sequentially in both cases. Memory access is similar either way.

The big difference is the control flow predictability.

Why Java shows a similar effect

This is not specific to C++. Java code also ends up running on real hardware, and the CPU still experiences branches and branch prediction. The Java JIT compiler may generate different machine code than a C++ compiler, but the underlying hardware behavior is the same.

Why the result can vary

The exact speedup depends on:

• CPU architecture
• compiler optimization level
• whether the compiler replaces the branch with branchless code
• data distribution
• surrounding code

So the effect is real, but the exact multiplier is not universal.

Imagine a toll road with two lanes:

• the left lane is for values < 128
• the right lane is for values >= 128

A worker tries to guess which lane each next car should go into.

Unsorted array

Cars arrive in random order:

• left n- right
• right
• left
• left
• right

The worker keeps guessing wrong, traffic stops, and cars need to be redirected. That is like branch misprediction.

Sorted array

Now cars arrive in a much more organized pattern:

• a long stream goes left
• then a long stream goes right

The worker quickly learns the pattern and keeps traffic moving. That is like good branch prediction.

The amount of work is logically the same, but the road flows much more smoothly.

The key syntax is a conditional branch inside a loop:

for (int i = 0; i < n; ++i) {
    if (data[i] >= 128)
        sum += data[i];
}

Example with unsorted data

#include <iostream>

int main() {
    int data[] = {130, 12, 200, 7, 128, 5, 250, 1};
    int sum = 0;

    for (int i = 0; i < 8; ++i) {
        if (data[i] >= 128)
            sum += data[i];
    }

    std::cout << sum << '\n';
}

The condition results are:

• true
• false
• true
• false
• true
• false
• true
• false

That alternating pattern is harder for the CPU to predict.

Example with sorted data

#include <iostream>

int main() {
    int data[] = {1, 5, 7, 12, 128, 130, 200, 250};
    int sum = 0;

    for (int i = 0; i < 8; ++i) {
        if (data[i] >= 128)
            sum += data[i];
    }

    std::cout << sum << '\n';
}

Now the condition results are:

• false
• false
• false
• false
• true
• true
• true
• true

That pattern is easier to predict.

Branchless style

Sometimes compilers or programmers use a branchless expression:

sum += (data[i] >= 128) ? data[i] : 0;

This may compile into machine code that avoids a hard branch, depending on the compiler and CPU. When that happens, sorted vs unsorted data may matter less.

Another branchless example

sum += data[i] * (data[i] >= 128);

In C++, the boolean expression becomes 0 or 1 in arithmetic contexts. This can remove unpredictable branching, although it is not always the fastest approach in every situation.

Consider this small example:

int data[] = {3, 180, 20, 140, 8, 200};
int sum = 0;

for (int i = 0; i < 6; ++i) {
    if (data[i] >= 128)
        sum += data[i];
}

Step-by-step

Iteration 1

• data[0] is 3
• 3 >= 128 is false
• do not add anything
• sum = 0

Iteration 2

• data[1] is 180
• 180 >= 128 is true
• add 180
• sum = 180

Iteration 3

• data[2] is 20
• condition is false
• sum = 180

Iteration 4

• data[3] is 140
• condition is true
• sum = 320

Iteration 5

• data[4] is 8
• condition is false
• sum = 320

Iteration 6

• data[5] is 200
• condition is true
• sum = 520

What the CPU sees

The branch outcomes are:

• false
• true
• false
• true
• false
• true

That is unpredictable.

Now sort it:

int data[] = {3, 8, 20, 140, 180, 200};

The outcomes become:

• false
• false
• false
• true
• true
• true

Now the CPU can predict much better.

Why the repeated outer loop matters

In your original benchmark, the inner loop runs over the same array 100000 times. That means the branch pattern repeats over and over:

• random pattern for unsorted data
• highly predictable pattern for sorted data

A predictable pattern gives the CPU many chances to run efficiently.

This effect appears in many real programs whenever code branches based on data.

Filtering records

if (user.age >= 18)
    adults.push_back(user);

If the input is grouped by age range, the branch may be more predictable than if users are randomly ordered.

Image or signal processing

if (pixel > threshold)
    brightCount++;

Threshold checks on ordered or partially ordered data can be faster than on random data.

Log processing

if (entry.level == ERROR)
    handleError(entry);

If log entries are grouped by severity, branch behavior becomes more regular.

Data cleanup pipelines

if (!value.empty())
    process(value);

Missing/non-missing data patterns can affect branch predictability.

Numerical computing

if (x > 0)
    sum += x;

A random sign distribution may perform differently from grouped positive and negative values.

In all of these cases, the work done is similar, but the order of the data can change how efficiently the CPU executes the code.

In real projects, developers often deal with this concept indirectly rather than manually sorting just for branch prediction.

Common patterns

1. Filtering with predictable data

If data is naturally grouped, loops with conditions may run faster without any special effort.

2. Guard clauses

Developers often write early checks like:

if (items.empty())
    return;

or:

if (!isValid(input))
    return false;

These are branches too, but usually they are highly predictable and cheap.

3. Validation passes

Code that validates large arrays or records often contains repeated conditions. If the data is noisy and random, branches may become expensive.

4. Branchless hot loops

In performance-critical code, developers may avoid unpredictable branches:

sum += (data[i] >= 128) ? data[i] : 0;

or use SIMD/vectorized approaches.

5. Partitioning instead of full sorting

If the only goal is to separate values by a condition, developers may use partitioning rather than sorting:

std::partition(data.begin(), data.end(), [](int x) {
    return x < 128;
});

This groups values by condition without fully ordering them.

6. Profiling before changing code

Real codebases rely on measurements. A branchless rewrite or data reordering can help, but only if profiling shows the loop is actually hot.

Practical lesson

Developers usually do not sort data just to make a branch faster unless the same ordered data will be reused many times. But they do care about:

• branch-heavy hot loops
• predictable control flow
• vectorization opportunities
• benchmarking with realistic data

1. Assuming this is mainly a cache effect

A common guess is that sorted data is faster because it is "more in cache." In this example, both versions scan the array sequentially, so cache behavior is very similar.

The bigger issue is usually branch prediction.

2. Thinking source-level work equals CPU-level work

These two pieces of code look like they should cost the same:

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

and

sum += (data[i] >= 128) ? data[i] : 0;

But the generated machine code may be very different. One may branch; another may use conditional move or arithmetic.

3. Benchmarking without optimization

If you compare performance without compiler optimizations, results may be misleading.

Use release settings such as:

g++ -O2 file.cpp

or

g++ -O3 file.cpp

and verify what the compiler actually generated.

4. Using a benchmark the compiler can simplify away

If sum is never used, a compiler might remove the loop entirely.

Broken benchmark example:

for (int i = 0; i < n; ++i) {
    if (data[i] >= 128)
        sum += data[i];
}
// sum never used

Always use or print the result so the computation remains necessary.

5. Assuming sorted data is always faster

Not always. Some cases where the effect may be smaller or disappear:

• the compiler generates branchless code
• the CPU predicts the branch well enough already
• memory access dominates the runtime
• vectorization changes the implementation

6. Sorting when it is not worth the cost

Sorting is O(n log n), while one pass over the array is O(n). If you only need one pass, sorting just to improve branch prediction is often a bad trade-off.

7. Forgetting that data distribution matters

This benchmark uses values from a small range and a threshold near the middle. That creates a branch that is close to 50/50, which is especially hard to predict.

If almost all values were above 128 or almost all below it, the branch would be much easier to predict even without sorting.

if branch vs branchless expression

Sorting vs partitioning

Algorithmic complexity

If your only goal is to process values above a threshold, sorting may improve branch predictability but still be a net loss unless the reordered data will be reused many times.

Main idea

A sorted array can be faster to process because branch outcomes become predictable.

Typical hot-loop pattern

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

Why sorted data helps

• unsorted random data -> branch is hard to predict
• sorted data -> long run of false, then long run of true
• fewer branch mispredictions -> faster execution

Not usually the main cause here

• not primarily cache
• not primarily language-specific behavior
• not because the sum changes

CPU concept to remember

• correct branch prediction: pipeline keeps flowing
• wrong branch prediction: pipeline flush, wasted work

When the effect is strongest

• data is random
• branch result is near 50/50
• the loop is repeated many times
• the compiler emits an actual branch

When the effect may shrink

• branchless machine code
• vectorization
• memory bandwidth dominates
• data is already biased mostly true or mostly false

Useful alternatives

sum += (data[i] >= 128) ? data[i] : 0;

std::partition(data.begin(), data.end(), [](int x) {
    return x < 128;
});

Rule of thumb

Do not sort only for this effect unless:

• the reordered data will be reused many times, or
• profiling proves it is worth it.

Why does sorting make the loop faster if the result is the same?

Because the CPU cares not only about what work is done, but also how predictable the control flow is. Sorting makes the if condition more predictable.

Is this a cache optimization?

Usually not in this example. Both versions read the array sequentially, so memory locality is already good. The bigger effect is branch prediction.

Why does the branch become hard to predict on random data?

Because values above and below the threshold appear in an irregular order, so the CPU often guesses the wrong path.

Does this happen only in C++?

No. It can also happen in Java, C, Rust, and other languages because the code ultimately runs on CPUs with branch predictors.

Can the compiler remove this problem?

Sometimes. A compiler may generate branchless code or vectorized code, which reduces or eliminates the difference between sorted and unsorted input.

Is sorting worth it just to speed up one loop?

Usually no. Sorting costs more than a single linear pass. It only makes sense if you will reuse the ordered data enough times.

Would std::partition be better than std::sort here?

If you only want to group values by a threshold, yes, partitioning is often a better fit because it is linear time and does not fully sort the array.

Why do modern compilers sometimes show a smaller difference?

Because newer compilers may produce better machine code, including branchless instructions or vectorized loops, which reduce dependence on branch prediction.

• Branch prediction — The main CPU feature that explains why sorted input can be faster.
• CPU pipeline — Helps explain why a mispredicted branch wastes work.
• Branch misprediction — The direct performance penalty behind this effect.
• Compiler optimization — Determines whether the code uses an actual branch or a branchless alternative.
• Vectorization — Can process many values at once and reduce branch costs.
• Cache locality — Often confused with branch prediction, but still important in performance work.
• Big-O complexity — Useful for understanding why sorting may not be worth it for a single pass.
• std::partition — A related algorithm when you only need to separate values by a condition.
• Benchmarking and profiling — Necessary to verify whether an optimization really helps in practice.