ArrayList.Sort should be a stable sort with an IComparer but is not?

Question

A stable sort is a sort that maintains the relative ordering of elements with the same value.

The docs on ArrayList.Sort say that when an IComparer is provided the sort is stable:

If comparer is set to null, this method performs a comparison sort (also called an unstable sort); that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal. To perform a stable sort, you must implement a custom IComparer interface.

Unless I'm missing something, the following testcase shows that ArrayList.Sort is not using a stable 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
    }
}

Am I missing something? If not, would this be a documentation bug or a library bug?

Apparently using an OrderBy in Linq gives a stable sort.

Answer 1

What the documentation appears to be saying is that the only way you can get a stable sort with ArrayList.Sort is to use an IComparer that somehow 'knows' the indices of the items that are being compared (one would imagine accomplishing this by making it run an initial pass on the collection) and uses that information as a tie-breaker for otherwise equal elements.

Although I agree that the phrasing of the documentation leaves much to be desired, it really doesn't make sense that any old comparer that doesn't consider the indices of the items to be compared can magically turn an inherently unstable sorting algorithm (which is what Arraylist.Sort is) into a stable one.