Why is processing a sorted array faster than processing an unsorted array in Java

In this tutorial we are going to learn about sorted array and unsorted array’s processing time.

This question is independent of Java and is not always true. Processing things in order can be faster for certain problems. Searching for items in a sorted array O(log N) instead of O(N) for unsorted which is the usual benefit for sorting. Other issues could be getting many short jobs done before starting long jobs can be more efficient.

Think of a telephone book

All the names sorted. look for ‘johnson’ in the book. I bet it will take you less than 3 minutes. as you know where J is in the alphabet

Now pretend you have those same 60,000 names and phone numbers - unsorted in the same type of book, all jumbled up. no particular order

Now go find johnson in the book. I bet it will take you hours!

as it could be on page 3, or page 349., you never know where it is.

Here is the example:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}