Почему при заказе с помощью Linq-to-Objects элементы сравниваются сами с собой?

В источнике ссылок QuickSort метод, используемый OrderBy, вы можете увидеть эти две строки:

while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;

Эти циклы while выполняются до тех пор, пока не найдут элемент, который больше не является «больше» (соответственно «меньше»), чем тот, на который указывает x. Поэтому они сломаются при сравнении идентичного элемента.

Я не могу доказать это математически, но полагаю, что избегание сравнения идентичных элементов сделало бы алгоритм более сложным и добавило бы накладные расходы, которые повлияют на производительность больше, чем это единственное сравнение.
(Обратите внимание, что ваш компаратор должен быть реализован достаточно умно, чтобы быстро вернуть 0 для идентичных элементов)

В первом случае перед разделителем -- выполняется четыре сравнения. Два из них сравнивают запись с самой собой («Strings: Bravo vs Bravo»). Почему?

Эффективность. Конечно, можно было бы сначала проверить, что объект не является самим собой, но это означает выполнение дополнительной операции при каждом сравнении, чтобы избежать случая, который возникает относительно редко и который в большинстве случаев довольно дешев (большинство компараторов). Это был бы чистый убыток.

(Между прочим, я экспериментировал именно с таким изменением алгоритма, и при измерении это действительно означало потерю эффективности при обычных сравнениях, таких как компаратор по умолчанию int).

Во втором случае никогда не должно возникать необходимости прибегать к сравнению Q-свойств (целых чисел); поскольку в значениях P нет дубликатов (относительно порядкового сравнения), поэтому никогда не требуется разрыва связей из ThenBy. Тем не менее мы дважды видим «Ints: 9 vs 9». Зачем использовать компаратор ThenBy с идентичными аргументами?

Кто сказал, что нет дубликатов? Внутреннему сравнению были даны две вещи (не обязательно ссылочные типы, поэтому короткое замыкание по ссылочной идентичности не всегда возможно) и есть два правила, которым нужно следовать. Первое правило требовало тай-брейка, поэтому тай-брейк был сделан.

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

Если известно, что для OrderBy не будет эквивалентных значений, то человек, который знает это, не должен использовать ненужное ThenBy, поскольку он потенциально может это знать.

Хорошо, давайте посмотрим на возможности здесь:

1. T — тип значения

   Чтобы проверить, сравнивает ли он элемент с самим собой, сначала необходимо проверить, являются ли оба элемента одним и тем же. Как бы Вы это сделали?

   Вы можете сначала вызвать Equals, а затем CompareTo, если элементы не совпадают. Вы действительно хотите это сделать? Стоимость Equals будет примерно такой же, как при сравнении, так что вы фактически удвоите стоимость заказа для чего именно? OrderBy просто сравнивает все элементы, и точка.

2. T — это ссылочный тип

   c# не позволяет вам перегружаться только общими ограничениями, поэтому вам нужно будет проверить во время выполнения, является ли T ссылочным типом или нет, а затем вызвать конкретную реализацию, которая изменит поведение, описанное выше. Вы хотите нести эти расходы в каждом случае? Конечно, нет.

   Если сравнение обходится дорого, внедрите в свою логику сравнения оптимизацию ссылок, чтобы избежать глупых затрат при сравнении элемента с самим собой, но этот выбор должен быть за вами. Я почти уверен, что string.CompareTo делает именно это.

Я надеюсь, что это сделает мой ответ более ясным, извините за предыдущий короткий ответ, мои рассуждения не были такими очевидными.

Проще говоря в случае 1

var coStr = Comparer<string>.Create((x, y) =>
{
    Console.WriteLine($"Strings: {x} versus {y}");
    return string.CompareOrdinal(x, y);
});

Мы просто сравниваем элементы, и нет условий для игнорирования, если результат равен 0. Таким образом, условие Console.WriteLine не зависит от результата сравнения. Если вы измените свой код, как показано ниже

var coStr = Comparer<string>.Create((x, y) =>
{
   if (x != y)
      Console.WriteLine($"Strings: {x} versus {y}");
   return string.CompareOrdinal(x, y);
});

Ваш вывод будет похож на

Strings: Bravo versus Alpha
Strings: Bravo versus Charlie

То же самое для второго оператора, здесь мы проверяем вывод обоих, поэтому для сравнения строк будет возвращено 0, затем оно пойдет для сравнения, поэтому оно возьмет это и выведет требуемое. Надеюсь, это рассеет ваши сомнения :)