.NET中OrderedEnumerable的ElementAt()行为异常原因及定性咨询

今年完成Advent of Code第5个任务时，我发现一个奇怪的行为：当使用不满足传递性的比较器对Enumerable进行排序后，ElementAt方法返回的顺序与实际枚举的顺序不一致——仅ElementAt(0)会重定向到First()，结果符合排序预期，其他索引的返回值完全不符合预期。

以下是可复现的示例代码（.NET 8.0）：

public class UnitTest1
{
    [Fact]
    public void Test1()
    {
        List<int> original = [2, 3, 1];
        var sorted = original.Order(new MyComparer());
        Assert.Equal("1,2,3", string.Join(',', sorted));    // 断言成功，看起来排序是对的？（其实不对）
        var enumerator = sorted.GetEnumerator();
        for (int i = 1; i <= 3; i++)
        {
            enumerator.MoveNext();
            Assert.Equal(i, enumerator.Current);    // 同样断言成功
        }
        Assert.Equal(1, sorted.First());        // 断言成功
        Assert.Equal(1, sorted.ElementAt(0));   // 断言成功
        Assert.Equal(2, sorted.ElementAt(1));   // 断言失败，实际返回3
        Assert.Equal(3, sorted.ElementAt(2));   // 断言失败，实际返回1？？？
    }

    private class MyComparer : IComparer<int>
    {
        public int Compare(int left, int right)
        {
            if (left == 1 && right == 2) return -1;
            else if (left == 2 && right == 3) return -1;
            else if (left == 3 && right == 2) return 1;
            else if (left == 2 && right == 1) return 1;
            else return 0;
        }
    }
}

问题分析 #

1. 核心原因：违反比较器的全序契约

.NET的LINQ Order方法要求传入的IComparer<T>必须满足全序关系，其中传递性是核心要求之一：若a < b且b < c，则必须a < c。

你的MyComparer明显不满足传递性：比如1和3比较时返回0（认为两者等价），但按照比较器逻辑，1 < 2且2 < 3，根据传递性应该1 < 3，但比较器未处理该场景，直接返回0，打破了排序算法的核心假设。

2. 不同方法的行为差异

• 直接枚举/string.Join/First()：
  当你直接枚举排序后的序列（包括string.Join遍历、GetEnumerator手动枚举、First()）时，LINQ会触发一次完整的排序流程，生成一个符合当前比较器临时逻辑的有序列表，因此结果看起来符合预期。

• ElementAt(n)（n>0）：
  ElementAt的实现逻辑是：若序列是IList<T>则直接索引访问，否则遍历到指定位置。但关键在于——Order返回的是延迟执行的序列，每次调用ElementAt都会重新执行一次排序！

  由于比较器不满足传递性，排序算法（如快速排序、归并排序等）的稳定性和正确性无法保证，每次排序可能生成不同的中间结果。因此第二次、第三次调用ElementAt时，重新排序后的序列与第一次枚举的序列完全不同，才会出现返回3、1的诡异结果。

行为定性：未定义行为，而非Bug #

这属于符合“鼻恶魔规则”的未定义行为，不是.NET的Bug。.NET官方文档明确规定，Order方法的比较器必须遵守IComparer<T>的契约（包括传递性、自反性、对称性）。一旦违反这个前置条件，程序的任何行为都是不可预测的——返回错误结果、崩溃甚至更奇怪的表现都在预期之内。

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