Warum ist die Verarbeitung einer sortierten array langsamer als in einem unsortierten array?

Habe ich eine Liste von 500000 zufällig generierte Tuple<long,long,string> Objekte, auf die trete ich ein einfaches "zwischen" - Suche:

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

Wenn ich die Erstellung meiner random array und führe meine Suche nach 100 zufällig generierte Werte x die Suche wird abgeschlossen in ungefähr vier Sekunden. Die Kenntnis der große Wunder, dass der die Sortierung der Suche, jedoch, ich beschloss, meine Daten Sortieren - zuerst durch Item1, dann durch Item2, und schließlich durch Item3 - vor dem ausführen von meinen 100 suchen. Ich erwartete die sortierte version durchführen ein wenig schneller, da der branch prediction: mein denken war, dass, sobald wir zu dem Punkt, wo Item1 == x alle weiteren Prüfungen t.Item1 <= x würde sagen der Zweig korrekt als "nicht nehmen", die Beschleunigung der Rute Teil der Suche. Viel zu meiner überraschung, die Suche dauerte doppelt so lange auf ein sortiertes array!

Ich habe versucht, schalten um die Reihenfolge, in der ich lief, meine Experimente und die verschiedenen verwendeten seed für den Zufallszahlengenerator, aber der Effekt ist der gleiche: Suche in einem unsortierten array lief fast doppelt so schnell wie die Suche in den gleichen array, aber sortiert!

Hat jemand eine gute Erklärung für diesen seltsamen Effekt? Der source-code meines tests folgt, ich bin mit .NET 4.0.

---

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<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> 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<Tuple<long,long,string>>(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 > 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 => t.Item1 <= x && t.Item2 >= 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);
}

---

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)