ArrayList.Sort应该是一个IComparer的稳定排序,但不是？

Question

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

ArrayList.Sort上的文档说当IComparer提供a时,排序是稳定的:

如果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
    }
}

我错过了什么吗？如果没有,这会是文档错误还是库错误？

显然在Linq中使用OrderBy可以提供稳定的排序.

Answer 1

什么是文件似乎说的是,只有这样,你可以得到一个稳定的排序与ArrayList.Sort是使用IComparer以某种方式"知道"被比较的项目的索引(一个想象通过使它运行初始通实现这一在集合上)并使用该信息作为其他相同元素的平局.

虽然我同意文档的措辞有很多不足之处,但任何不考虑要比较的项目索引的旧比较器都可以神奇地变成一种固有的不稳定排序算法(这是什么Arraylist.Sort是稳定的.