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 в Linq дает стабильную сортировку.

Answer 1

Документация говорит о том, что единственный способ получить стабильную сортировку с ArrayList.Sort это использовать IComparer он каким-то образом "знает" индексы сравниваемых элементов (можно было бы представить, что это выполняется путем запуска первоначального прохода по коллекции) и использует эту информацию в качестве прерывателя связей для в противном случае равных элементов.

Хотя я согласен с тем, что формулировка документации оставляет желать лучшего, на самом деле не имеет смысла, что любой старый компаратор, который не учитывает индексы сравниваемых элементов, может волшебным образом превратить изначально нестабильный алгоритм сортировки (который является какие Arraylist.Sort есть) в стабильный.