ArrayList.Sort 应该是带有 IComparer 的稳定排序，但事实并非如此？

Question

稳定排序是一种维护具有相同值的元素的相对顺序的排序。

ArrayList.Sort 上的文档说，当 IComparer 假设排序是稳定的：

如果Comparer设置为null，则该方法执行比较排序（也称为不稳定排序）；也就是说，如果两个元素相等，它们的顺序可能不会保留。相反，稳定排序会保留相等元素的顺序。要执行稳定的排序，您必须实现自定义 IComparer 接口。

除非我遗漏了什么，否则以下测试用例表明 ArrayList.Sort 未使用稳定的排序：

internal class DisplayOrdered {
    public int ID { get; set; }
    public int DisplayOrder { get; set; }
    public override string ToString() {
        return string.Format("ID: {0}, DisplayOrder: {1}", ID, DisplayOrder);
    }
}

internal class DisplayOrderedComparer : IComparer {
    public int Compare(object x, object y) {
        return ((DisplayOrdered)x).DisplayOrder - ((DisplayOrdered)y).DisplayOrder;
    }
}

[TestFixture]
public class ArrayListStableSortTest {

    [Test]
    public void TestWeblinkCallArrayListIsSortedUsingStableSort() {
        var call1 = new DisplayOrdered {ID = 1, DisplayOrder = 0};
        var call2 = new DisplayOrdered {ID = 2, DisplayOrder = 0};
        var call3 = new DisplayOrdered {ID = 3, DisplayOrder = 2};
        var list = new ArrayList {call1, call2, call3};

        list.Sort(new DisplayOrderedComparer());

        // expected order (by ID): 1, 2, 3 (because the DisplayOrder
        // is equal for ID's 1 and 2, their ordering should be
        // maintained for a stable sort.)
        Assert.AreEqual(call1, list[0]); // Actual: ID=2 ** FAILS 
        Assert.AreEqual(call2, list[1]); // Actual: ID=1
        Assert.AreEqual(call3, list[2]); // Actual: ID=3
    }
}

我遗漏了什么吗？如果不是，这会是文档错误还是库错误？

显然使用 OrderBy 提供稳定的排序。

Answer 1

文档似乎说的是，使用 ArrayList.Sort 获得稳定排序的唯一方法是使用以某种方式“知道”索引的 IComparer正在比较的项目（可以想象通过使其在集合上运行初始传递来实现这一点），并使用该信息作为其他相同元素的决胜局。

尽管我同意文档的措辞还有很多不足之处，但任何不考虑要比较项目的索引的旧比较器都可以神奇地变成一个没有意义的东西。将本质上不稳定的排序算法（这就是Arraylist.Sort）转换为稳定的算法。