c# - 为什么使用 Linq-to-Objects 进行排序会将项目与自身进行比较？

Question

考虑以下使用 LINQ OrderBy 和 ThenBy 的简单代码:

static void Main()
{
  var arr1 = new[] { "Alpha", "Bravo", "Charlie", };

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

  arr1.OrderBy(x => x, coStr).ToList();

  Console.WriteLine("--");

  var arr2 = new[]
  {
    new { P = "Alpha", Q = 7, },
    new { P = "Bravo", Q = 9, },
    new { P = "Charlie", Q = 13, },
  };

  var coInt = Comparer<int>.Create((x, y) =>
  {
    Console.WriteLine($"Ints: {x} versus {y}");
    return x.CompareTo(y);
  });

  arr2.OrderBy(x => x.P, coStr).ThenBy(x => x.Q, coInt).ToList();
}

这只是使用一些比较器，将它们比较的内容写到控制台。

在我的硬件和框架版本 (.NET 4.6.2) 上，这是输出:

Strings: Bravo versus Alpha
Strings: Bravo versus Bravo
Strings: Bravo versus Charlie
Strings: Bravo versus Bravo
--
Strings: Bravo versus Alpha
Strings: Bravo versus Bravo
Ints: 9 versus 9
Strings: Bravo versus Charlie
Strings: Bravo versus Bravo
Ints: 9 versus 9

我的问题是:为什么他们会将查询中的项目与自身进行比较？

在第一种情况下，在-- 分隔符之前，他们进行了四次比较。其中两个将条目与自身进行比较(“Strings: Bravo versus Bravo”)。为什么？

在第二种情况下，永远不需要求助于比较 Q 属性(整数)；因为在 P 值中没有重复(wrt.ordinal 比较)，所以永远不需要从 ThenBy 中打破平局。我们仍然两次看到“整数:9 对 9”。为什么使用具有相同参数的 ThenBy 比较器？

注意:任何比较器在与自身进行比较时都必须返回 0。因此，除非算法只是想检查我们是否正确实现了比较器(无论如何它永远无法完全做到)，否则发生了什么？

请注意:在我的示例中，查询生成的元素中没有重复项。

我在另一个示例中看到了同样的问题，查询产生了更多条目。以上我只是举了一个小例子。这也发生在生成偶数 个元素的情况下。

Answer 1

在reference source在 OrderBy 使用的 QuickSort 方法中，您可以看到这两行:

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

这些 while 循环会一直运行，直到找到一个不再比 x 指向的元素“更大”(resp.“更小”)的元素。因此，当比较相同 元素时，它们会中断。

我无法从数学上证明它，但我想避免比较相同的元素会使算法更加复杂，并引入开销，这比这种单一比较对性能的影响更大。
(请注意，您的比较器应该实现得足够聪明，以便为相同的元素快速返回 0)