Pourquoi le traitement d'un tableau trié plus lent qu'un tableau non trié?

J'ai une liste de 500000 objets Tuple<long,long,string> générés aléatoirement sur lesquels j'effectue une simple recherche "entre":

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

Lorsque je génère mon tableau aléatoire et lance ma recherche pour 100 valeurs générées aléatoirement de x, les recherches se terminent en environ quatre secondes. Connaissant les grandes merveilles que le tri fait à la recherche , cependant, j'ai décidé de trier mes données - d'abord par Item1, puis par Item2, et enfin par Item3 - avant d'exécuter mes 100 recherches. Je m'attendais à ce que le trié version pour effectuer un peu plus vite à cause de la prédiction de la branche: ma pensée a été qu'une fois que nous arrivons au point où Item1 == x, toutes les vérifications supplémentaires de t.Item1 <= x prédiraient la branche correctement comme "pas de prise", accélérant la partie arrière de la recherche. À ma grande surprise, les recherches ont pris deux fois plus de temps sur un tableau trié !

J'ai essayé de changer l'ordre dans lequel j'ai couru mes expériences, et utilisé une graine différente pour le générateur de nombres aléatoires, mais l'effet a été le idem: les recherches dans un tableau non trié ont été presque deux fois plus rapides que les recherches dans le même tableau, mais triées!

Quelqu'un a-t-il une bonne explication de cet effet étrange? Le code source de mes tests suit; j'utilise. 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)