_FR>Порассуждайте сами: OrderBy вычитывает переданную последовательность в буфер, сортирует и возвращает. По другому она в принципе не может работать.
Есть и другие реализации LINQ, например LinqBridge. Там при сортировке keySelector выполняется для каждого сравнения (пока).
_FR>Зачем вам использовать её для перемешивания элементов и задаваться непонятными вопросами, когда вам достаточно так же сомому вычитать последовательность с буфер, перемешать и возвратить перемешанное, не бребегая к OrderBy вовсе?
Здесь вы правы, для перемешивания действительно лучше использовать алгоритм перемешивания.
