Р>Вообщем, я озадачен. Есть предположения почему так?

не вижу в коде замера времени. ты вместе с запуском и завершением процесса мерил, что ли?
замерь строго вызов метода Sort(), причем как минимум второго вызова (при первом может работать JIT) и надежнее несколько замеров в цикле сделать