¿Por qué procesar una matriz ordenada es más lento que una matriz sin clasificar?

Tengo una lista de 500000 objetos generados aleatoriamente Tuple<long,long,string> en los que estoy realizando una simple búsqueda" entre":

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

Cuando genero mi matriz aleatoria y corro mi búsqueda de 100 valores generados aleatoriamente de x, las búsquedas se completan en unos cuatro segundos. Sabiendo de las grandes maravillas que la ordenación hace a la búsqueda , sin embargo, decidí ordenar mis datos - primero por Item1, luego por Item2, y finalmente por Item3 - antes de ejecutar mis 100 búsquedas. Me esperaba el ordenado versión para realizar un poco más rápido debido a la predicción de ramas: mi pensamiento ha sido que una vez que lleguemos al punto donde Item1 == x, todas las comprobaciones adicionales de t.Item1 <= x predecirían la rama correctamente como "no toma", acelerando la porción de cola de la búsqueda. Para mi sorpresa, las búsquedas tomaron el doble de tiempo en una matriz ordenada!

Intenté cambiar el orden en el que ejecuté mis experimentos, y usé diferentes semillas para el generador de números aleatorios, pero el efecto ha sido el lo mismo: las búsquedas en una matriz sin clasificar se ejecutaron casi el doble de rápido que las búsquedas en la misma matriz, ¡pero ordenadas!

¿alguien tiene una buena explicación de este extraño efecto? El código fuente de mis pruebas sigue; estoy usando. 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)