7

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.

Community
  • 1
  • 1
Kaleb Pederson
  • 45,767
  • 19
  • 102
  • 147
  • 1
    Is it possible that the intent of the comment may be "you need to implement your own IComparer that forces the sort to be stable" and not "if you implement your own IComparer, the sort will be stable implicitly"? – BlueMonkMN Feb 18 '11 at 23:21
  • 3
    That's not a good way to implement Compare. http://blogs.msdn.com/b/ericlippert/archive/2011/01/27/spot-the-defect-bad-comparisons-part-three.aspx – Mark Byers Feb 18 '11 at 23:21
  • Are you sure you're not falling into the fallacy described here: http://blogs.msdn.com/b/ericlippert/archive/2011/01/27/spot-the-defect-bad-comparisons-part-three.aspx EDIT: Bah, got beaten to the punch while trying to find the link. :D – Jeff Hubbard Feb 18 '11 at 23:22
  • 1
    @Mark - Eric's points make some good points some of which I wasn't aware of. I actually changed the comparer for this post from using System.Integer32.CompareTo() because I thought it might be easier to understand. Guess I should have left it. – Kaleb Pederson Feb 18 '11 at 23:24
  • @Mark Wow, I wish I could +1 you for that link. I always thought subtraction to be a convenient, "computery" way to represent comparisons. `glow.levelUp();` Thanks! – corsiKa Feb 18 '11 at 23:25
  • @Jeff - In this case no, we're dealing with small positive integers ... although I could have easily fallen into that trap, in reality we're delegating to a system comparison implementation. – Kaleb Pederson Feb 18 '11 at 23:29
  • @Henk Holterman: Sure, and as long as your integers are single digits you could also convert them to strings and then compare the strings - that will work fine for 0 to 9. However just because you *can* do something doesn't mean you *should* especially when the correct way is really, really easy. – Mark Byers Feb 18 '11 at 23:40
  • @Kaleb @Henk Even so, subtraction doesn't guarantee overall ordering, which is exactly what the initial problem is. – Jeff Hubbard Feb 18 '11 at 23:52
  • @Kaleb: If you're not using .NET 1.1, then you should not be using `ArrayList`. You should use `List` instead, if you need a list of different types of object, otherwise, you should use `List`, where `T` is the type of object. – John Saunders Feb 19 '11 at 00:24

1 Answers1

9

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.

Ani
  • 111,048
  • 26
  • 262
  • 307
  • 2
    Indeed. The current implementation of `ArrayList.Sort` simply calls out to `Array.Sort` regardless of the `IComparer` used. `Array.Sort` is more explicitly documented as using an unstable QuickSort. http://msdn.microsoft.com/en-us/library/afwbytk2.aspx – LukeH Feb 19 '11 at 01:56
  • although certainly not what I would have assumed from the docs it seems a plausible interpretation. My assumption was that whenever an `IComparer` was passed in a stable sort would be used. But, as LukeH pointed out and looking at the source code reveals, that is not the case. – Kaleb Pederson Feb 20 '11 at 05:13