Why a Sorted Array is Processed Faster? Explanation with Java

Introduction: The Paradox That Blew Up Stack Overflow

Imagine: you write a simple Java loop that sums array elements based on a condition (e.g., if the number is greater than 128). You run the code on a sorted array — and it executes 2–3 times faster than on an unsorted array. Sounds like magic? In reality, it's not magic, but branch prediction — one of the key features of modern processors.

The question “Why is conditional processing of a sorted array faster than of an unsorted array?” received over 30,000 upvotes on Stack Overflow and became a classic for studying low-level optimization. In this article, we will not only break down the theory but also write real Java code to see the effect firsthand. And most importantly, you will learn how to use this knowledge in practice.

If you want to understand more deeply how Java code optimization works and why branch prediction can both speed up and slow down your program — you've come to the right place.

1. Experiment: The Code That Shows Everything

Let's start with a simple Java application. We will create two arrays: one sorted, the other random. Then we will iterate through each and calculate the sum of elements greater than a threshold value (e.g., 128). We will measure the execution time.

import java.util.Arrays;\nimport java.util.Random;\n\npublic class BranchPredictionDemo {\n    private static final int SIZE = 100_000;\n    private static final int THRESHOLD = 128;\n\n    public static void main(String[] args) {\n        // Create an unsorted array\n        int[] unsorted = new int[SIZE];\n        Random rand = new Random();\n        for (int i = 0; i < SIZE; i++) {\n            unsorted[i] = rand.nextInt(256); // 0..255\n        }\n\n        // Create a sorted array (copy and sort)\n        int[] sorted = unsorted.clone();\n        Arrays.sort(sorted);\n\n        // Measure time for unsorted\n        long start = System.nanoTime();\n        long sumUnsorted = processArray(unsorted);\n        long end = System.nanoTime();\n        System.out.println("Unsorted: " + (end - start) / 1_000_000 + " ms, sum = " + sumUnsorted);\n\n        // Measure time for sorted\n        start = System.nanoTime();\n        long sumSorted = processArray(sorted);\n        end = System.nanoTime();\n        System.out.println("Sorted: " + (end - start) / 1_000_000 + " ms, sum = " + sumSorted);\n    }\n\n    private static long processArray(int[] arr) {\n        long sum = 0;\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] >= THRESHOLD) {\n                sum += arr[i];\n            }\n        }\n        return sum;\n    }\n}\n

Results on my laptop (Intel i7, Java 17):

\n
• Unsorted array: ~22 ms
\n
• Sorted array: ~8 ms
\n

Almost a 3x difference! Why? The number of operations is the same. The answer lies in how the processor handles the condition if (arr[i] >= THRESHOLD).

2. Branch Prediction: The Processor's Brain

Modern processors use a pipeline architecture — they predict which execution path (branch) will be taken and start executing instructions ahead of time. If the prediction is correct — everything runs smoothly. If it's incorrect — the pipeline is flushed, and the processor wastes cycles on cleanup.

In a sorted array, values are first mostly below 128, and then mostly above. The processor quickly "learns": if the previous 1000 times were false, then the next one is likely false as well. The prediction works almost perfectly.

In an unsorted array, values randomly jump above and below the threshold. The processor is wrong in ~50% of cases, wh