Почему операции LINQ могут выполняться быстрее, чем обычный цикл?

Сегодня мы с другом были немного озадачены во время обсуждения программирования. В качестве примера мы создали фиктивную проблему наличия List n случайных целых чисел (обычно 1.000.000) и хотели создать функцию, которая возвращала бы набор всех целых чисел, которых было больше один из. Довольно простой материал. Мы создали один оператор LINQ для решения этой проблемы и простой алгоритм сортировки вставкой.

Теперь, когда мы проверили скорость выполнения кода (используя System.Diagnostics.StopWatch ), результаты были такими: сбивает с толку. Код LINQ не только превзошел простую сортировку, но и работал быстрее, чем единственный foreach / для , который выполнял только один цикл списка и не имел внутри операций (которые, как я полагал, компилятор должен был обнаружить и удалить все вместе).

Если бы мы сгенерировали новый List случайных чисел при том же выполнении программа и снова запустила код LINQ, производительность увеличится на порядки (обычно в тысячи раз). Производительность пустых петель, конечно же, была такой же.

Итак, что здесь происходит? Использует ли LINQ параллелизм, чтобы превзойти обычные циклы? Как вообще возможны такие результаты? LINQ использует быструю сортировку, которая выполняется при n * log (n), что по определению уже медленнее, чем n.

И что происходит при скачке производительности при втором запуске?

Мы были сбиты с толку и заинтригованы этими результатами и надеялись на разъяснения от сообщества, просто чтобы удовлетворить наше любопытство.