title: Why is processing a sorted array faster than processing an unsorted array?
body: <p>Here is a piece of C++ code that shows some very peculiar behavior. For some strange reason, sorting the data (<em>before</em> the timed region) miraculously makes the loop almost six times faster.</p>
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;algorithm&gt;
  #include &lt;ctime&gt;
  #include &lt;iostream&gt;
  
  int main()
  {
      // Generate data
      const unsigned arraySize = 32768;
      int data[arraySize];
  
      for (unsigned c = 0; c &lt; 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 &lt; 100000; ++i)
      {
          for (unsigned c = 0; c &lt; arraySize; ++c)
          {   // Primary loop
              if (data[c] &gt;= 128)
                  sum += data[c];
          }
      }
  
      double elapsedTime = static_cast&lt;double&gt;(clock()-start) / CLOCKS_PER_SEC;
  
      std::cout &lt;&lt; elapsedTime &lt;&lt; '\n';
      std::cout &lt;&lt; &quot;sum = &quot; &lt;&lt; sum &lt;&lt; '\n';
  }
  </code></pre>
  <ul>
  <li>Without <code>std::sort(data, data + arraySize);</code>, the code runs in 11.54 seconds.</li>
  <li>With the sorted data, the code runs in 1.93 seconds.</li>
  </ul>
  <p>(Sorting itself takes more time than this one pass over the array, so it's not actually worth doing if we needed to calculate this for an unknown array.)</p>
  <hr />
  <p>Initially, I thought this might be just a language or compiler anomaly, so I tried Java:</p>
  <pre class="lang-java prettyprint-override"><code>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 &lt; 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 &lt; 100000; ++i)
          {
              for (int c = 0; c &lt; arraySize; ++c)
              {   // Primary loop
                  if (data[c] &gt;= 128)
                      sum += data[c];
              }
          }
  
          System.out.println((System.nanoTime() - start) / 1000000000.0);
          System.out.println(&quot;sum = &quot; + sum);
      }
  }
  </code></pre>
  <p>With a similar but less extreme result.</p>
  <hr />
  <p>My first thought was that sorting brings the data into the <a href="https://en.wikipedia.org/wiki/CPU_cache" rel="noreferrer">cache</a>, but then I thought how silly that was because the array was just generated.</p>
  <ul>
  <li>What is going on?</li>
  <li>Why is processing a sorted array faster than processing an unsorted array?</li>
  </ul>
  <p>The code is summing up some independent terms, so the order should not matter.</p>
  <hr />
  <p><strong>Related / followup Q&amp;As</strong> about the same effect with different / later compilers and options:</p>
  <ul>
  <li><a href="https://stackoverflow.com/q/66521344">Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang?</a></li>
  <li><a href="https://stackoverflow.com/q/28875325">gcc optimization flag -O3 makes code slower than -O2</a></li>
  </ul>