A sorted array faster than an unsorted array ? Here’s a bit of Visual C++ code that strikes me as odd. Sorting the results, for some odd reason, makes the code almost six times faster.

``````#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];

for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;

// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);

// Test
clock_t start = clock();
long long sum = 0;

for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}``````
• Without std::sort(data, data + arraySize); the code runs in 11.54 seconds.
• With the sorted data, the code runs in 1.93 seconds.

I thought it could be a language or compiler issue at first, so I tried Java

``````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)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}

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

With a similar but less extreme result.

My first thought was that sorting the data into the cache would carry it into the cache, but I quickly realized that this was ridiculous because the array had just been created. So my question is : Why is processing a sorted array faster than processing an unsorted array ???

Answer : With a sorted array, the condition data[c] >= 128 is first false for a streak of values, then becomes true for all later values. That’s easy to predict. With an unsorted array, you pay for the branching cost.

A sorted array is one in which each element is sorted in some way, such as numerically, alphabetically, or both. Many algorithms exist for sorting a numerical array, including bubble sort, insertion sort, selection sort, merge sort, fast sort, heap sort, and so on..