Why is a sorted array processed faster than not sorted?

Here is an example of C ++ code that looks very strange. For some reason, when the data is sorted, the code runs almost six times faster.

#include <algorithm> #include <ctime> #include <iostream>  int main() {     // Заполнение данными     const unsigned arraySize = 32768;     int data[arraySize];      for (unsigned c = 0; c < arraySize; ++c)         data[c] = std::rand() % 256;      // !!! С этой строкой следующий цикл работает быстрее     std::sort(data, data + arraySize);      // Проверка     clock_t start = clock();     long long sum = 0;      for (unsigned i = 0; i < 100000; ++i)     {         // Основной цикл         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 11.54 seconds.
  • With sorted data – 1.93 seconds.

At first, I thought something was wrong with the language or the compiler. So I tried using Java.

import java.util.Arrays; import java.util.Random;  public class Main {     public static void main(String[] args)     {         // Заполнение данными         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;          // !!! С этой строкой следующий цикл работает быстрее         Arrays.sort(data);          // Проверка         long start = System.nanoTime();         long sum = 0;          for (int i = 0; i < 100000; ++i)         {             // Основной цикл             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);     } }

The result was similar results, but with a smaller gap.


My first thought was that when sorting, the data goes to the cache, but then I thought it was stupid, because the array was just created.

  • What’s happening?
  • Why is a sorted array processed faster than not sorted?

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

Asked on February 4, 2020 in Programming.
Add Comment
0 Answer(s)

Your Answer

By posting your answer, you agree to the privacy policy and terms of service.