title: Why is processing a sorted array slower than an unsorted array?
body: <p>I have a list of 500000 randomly generated <code>Tuple&lt;long,long,string&gt;</code> objects on which I am performing a simple "between" search:</p>
  
  <pre><code>var data = new List&lt;Tuple&lt;long,long,string&gt;&gt;(500000);
  ...
  var cnt = data.Count(t =&gt; t.Item1 &lt;= x &amp;&amp; t.Item2 &gt;= x);
  </code></pre>
  
  <p>When I generate my random array and run my search for 100 randomly generated values of <code>x</code>, the searches complete in about four seconds. Knowing of the <a href="https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array">great wonders that sorting does to searching</a>, however, I decided to sort my data - first by <code>Item1</code>, then by <code>Item2</code>, and finally by <code>Item3</code> - before running my 100 searches. I expected the sorted version to perform a little faster because of branch prediction: my thinking has been that once we get to the point where <code>Item1 == x</code>, all further checks of <code>t.Item1 &lt;= x</code> would predict the branch correctly as "no take", speeding up the tail portion of the search. Much to my surprise, <strong>the searches took twice as long on a sorted array</strong>!</p>
  
  <p>I tried switching around the order in which I ran my experiments, and used different seed for the random number generator, but the effect has been the same: searches in an unsorted array ran nearly twice as fast as the searches in the same array, but sorted!</p>
  
  <p>Does anyone have a good explanation of this strange effect? The source code of my tests follows; I am using .NET 4.0.</p>
  
  <hr>
  
  <pre><code>private const int TotalCount = 500000;
  private const int TotalQueries = 100;
  private static long NextLong(Random r) {
      var data = new byte[8];
      r.NextBytes(data);
      return BitConverter.ToInt64(data, 0);
  }
  private class TupleComparer : IComparer&lt;Tuple&lt;long,long,string&gt;&gt; {
      public int Compare(Tuple&lt;long,long,string&gt; x, Tuple&lt;long,long,string&gt; y) {
          var res = x.Item1.CompareTo(y.Item1);
          if (res != 0) return res;
          res = x.Item2.CompareTo(y.Item2);
          return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
      }
  }
  static void Test(bool doSort) {
      var data = new List&lt;Tuple&lt;long,long,string&gt;&gt;(TotalCount);
      var random = new Random(1000000007);
      var sw = new Stopwatch();
      sw.Start();
      for (var i = 0 ; i != TotalCount ; i++) {
          var a = NextLong(random);
          var b = NextLong(random);
          if (a &gt; b) {
              var tmp = a;
              a = b;
              b = tmp;
          }
          var s = string.Format("{0}-{1}", a, b);
          data.Add(Tuple.Create(a, b, s));
      }
      sw.Stop();
      if (doSort) {
          data.Sort(new TupleComparer());
      }
      Console.WriteLine("Populated in {0}", sw.Elapsed);
      sw.Reset();
      var total = 0L;
      sw.Start();
      for (var i = 0 ; i != TotalQueries ; i++) {
          var x = NextLong(random);
          var cnt = data.Count(t =&gt; t.Item1 &lt;= x &amp;&amp; t.Item2 &gt;= x);
          total += cnt;
      }
      sw.Stop();
      Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
  }
  static void Main() {
      Test(false);
      Test(true);
      Test(false);
      Test(true);
  }
  </code></pre>
  
  <hr/>
  
  <pre><code>Populated in 00:00:01.3176257
  Found 15614281 matches in 00:00:04.2463478 (Unsorted)
  Populated in 00:00:01.3345087
  Found 15614281 matches in 00:00:08.5393730 (Sorted)
  Populated in 00:00:01.3665681
  Found 15614281 matches in 00:00:04.1796578 (Unsorted)
  Populated in 00:00:01.3326378
  Found 15614281 matches in 00:00:08.6027886 (Sorted)
  </code></pre>