ArrayList.Sort should be a stable grade with IComparer, but no?

Question

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

The ArrayList.Sort docs say that under the condition of IComparer sorting is stable:

If the comparison parameter is set to null, this method performs sorting (also called unstable sorting); that is, if two elements are equal, their order may not be preserved. In contrast, robust sorting preserves the order of equal elements. To perform stable sorting, you must implement the IComparer user interface.

If I didn’t miss something, the following test case shows that ArrayList.Sort does not use a stable view:

 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 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, will it be a documentation error or a library error?

Using OrderBy in Linq seems to give a stable look.

Answer 1

The documentation seems to say that the only way to get stable sorting with ArrayList.Sort is to use IComparer , which somehow “knows” the indices of the items that are being compared (you could imagine doing this by starting the initial pass in compilation) and uses this information as a tie-breaker for other identical elements.

Although I agree that the wording of the documentation leaves much to be desired, it really does not make sense that any old comparator that does not take into account the indices of the elements being compared can magically turn an essentially unstable sorting algorithm (which is ArrayList.Sort ) into a stable .