Why is it faster to process a sorted array than an unsorted array?

manpreet Best Answer 2 years ago

Here is a piece of C++ code that seems very peculiar. For some strange reason, sorting the data miraculously makes the code almost six times faster.

#include 
#include <ctime>
#include 

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 com/tag/start">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(clock() - com/tag/start">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.

Initially, I thought this might be just a language or compiler anomaly. So I tried it in Java.

import com/tag/java">java.util.Arrays;
import com/tag/java">java.util.Random;

public com/tag/class">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
                                                

                                                                                                        
                                                    
                                                
                                                

                                                    

                                                        
                                                            0
                                                            views 

                                                            0
                                                                likes 
                                                            
                                                            

                                                            0
                                                            shares
                                                            


    

         Facebook
        
         Twitter
        
        
         Linked In 
        
          WhatsApp