为何List<T>.Sort()（T实现IComparable<T>）与传入IComparer<T>的排序结果不同？

问题背景 #

输入相同数据时，依赖IComparable<T>的List<T>.Sort()与传入IComparer<T>参数的List<T>.Sort()排序结果存在差异——差异仅体现在X、Y完全相同的元素的相对顺序上。所用的PointComparer不规范：对于X、Y相等的元素，它不会返回0，而是返回1。需要明确差异原因，同时希望通过替换为IComparable<T>实现来提升性能，且匹配原IComparer<T>的排序行为。

差异产生的核心原因 #

1. 比较器违反规范 #

标准的IComparer<T>必须满足三个核心规则：

• 自反性：Compare(a, a)必须返回0
• 对称性：Compare(a, b) == -Compare(b, a)
• 传递性：若Compare(a, b) <= 0且Compare(b, c) <= 0，则Compare(a, c) <= 0

你的PointComparer.Compare完全不满足自反性和对称性：当两个Point的X、Y都相同时，Compare(a, b)返回1，Compare(b, a)也返回1，这会让排序算法无法正确识别“等价元素”，进而对这些元素进行不必要的交换操作。

2. 不稳定排序的特性 #

.NET的List<T>.Sort()采用IntroSort（快速排序的变体），属于不稳定排序。不稳定排序不会保留等价元素的原始相对顺序，当比较器无法正确识别等价元素时，排序过程中元素的交换顺序完全依赖算法的执行路径，结果具有不确定性。

3. 两种Sort重载的内部实现差异 #

虽然你的Point.CompareTo直接委托给PointComparer.Default.Compare，但List<T>.Sort()的无参数重载与带IComparer<T>参数的重载，在内部调用比较逻辑的路径上存在细微差异：

• 无参数重载直接调用元素的CompareTo方法，JIT更容易进行内联优化，执行路径更直接
• 带IComparer<T>的重载需要通过接口调用Compare方法，存在额外的委托开销，且算法的分区逻辑可能因接口调用的包装层产生微小变化

这些差异在非规范比较器的放大下，最终导致等价元素的相对顺序出现差异。

能否修改CompareTo匹配IComparer的行为？ #

你的当前CompareTo实现已经完全复用了PointComparer.Compare的逻辑，从代码逻辑上看两者完全一致，但由于上述的内部实现差异和非规范比较器的影响，仍然无法保证排序结果完全一致。

如果必须让两种Sort调用的结果完全一致，有两种可行方向：

• 修正比较器规范性：在CompareTo中补充等价判断，当X、Y完全相同时返回0。但你提到无法修改原比较器逻辑，此方案不可行。
• 改用稳定排序：使用LINQ的OrderBy/ThenBy方法（稳定排序），可以保留等价元素的原始顺序，但性能略低于List<T>.Sort()。

性能优化的可行方案 #

若优先考虑性能，同时尽量贴近原排序逻辑，可尝试以下方案：

1. 复刻比较逻辑，减少委托开销 #

将PointComparer.Compare的逻辑直接写入CompareTo，避免委托调用的开销，提升JIT内联概率，进一步优化性能：

public int CompareTo(Point b)
{
    if (Y == b.Y)
    {
        return (X < b.X) ? -1 : 1;
    }
    return (Y > b.Y) ? -1 : 1;
}

此实现与原PointComparer逻辑完全一致，且性能比委托调用的版本更优。

2. 接受等价元素的顺序差异 #

如果业务逻辑允许X、Y相同的元素顺序存在微小差异，直接使用IComparable<T>的实现即可——它的性能确实远高于传入IComparer<T>的版本，因为减少了接口调用的间接开销，JIT优化空间更大。

内容的提问来源于stack exchange，提问作者MineR