Behaviour of List<T>.Sort in .NET 4.5 changed from .NET 4.0?

Question

I have the following test inside a project targeting .NET 4.0:

[TestFixture]
public class Donkey
{
    [Test]
    public void TestListSorting()
    {
        var expected = new[]
                    {
                                MockRepository.GenerateStub<IComparable>(),
                                MockRepository.GenerateStub<IComparable>()
                    };

        var sorted = new List<IComparable>(expected);

        CollectionAssert.AreEqual(expected, sorted);
        sorted.Sort();
        CollectionAssert.AreEqual(expected, sorted);

    }
}

If I run it on a machine with only .NET 4.0 installed, it fails. If I run it on a machine with only .NET 4.5 installed, it passes.

I am assuming that in .NET 4.5 the implementation of Sort has been changed to maintain order when sorting a list of objects which each return 0 from CompareTo.

Now, put aside the obvious insanity of this test. I know it's crazy to rely on this kind of behaviour.

Surely this is a breaking change? It is not listed on this page about compatibility between .NET 4.0 and 4.5.

Is there a reason for this? Am I missing something? Is there another page which shows actual breaking changes? Should I just have a sit down and stop panicking?

Answer 1

I've answered a similar question to this before. The sorting method has changed between 4.5 and 4.0, from a quick sort to an introspective sort.

It's actually faster, but still it is not a stable sort¹, that is, one that has the same output for every execution by preserving the order of equal items. Since no implementation of List.Sort is a stable sort, I don't think you've run your unit test above enough times to have it error in both runtimes?

I tried to reproduce it myself with equivalent code and a comparer that returns 0. Sometimes the list order is preserved and sometimes it is not, in both .NET 4.5 and .NET 3.5.

Even if it did change the sort type from stable to unstable, its not a breaking change. The type of sort used and the exact output is not part of the contract for List.Sort. All that the method contract guarantees is that your items will be in sorted order according to the comparer used.

It is interesting, though, because the [MSDN documentation](http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx) still says it uses QuickSort (via `Array.Sort`), but this is not the case if you were to step through the .NET reference source.

---

_{¹By definition of using a mix of QuickSort and HeapSort, it should be an unstable sort. Even David Musser, the designer of the algorithm states in his paper:}

_{Introsort, like quicksort, is not stable -- does not preserve the order of equivalent elements -- so there is still a need to have a separate requirement for a stable sorting routine.}

Answer 2

The spec for List.Sort says that the sort used is unstable and thus may not preserve the ordering of equal elements; it doesn't specify a particular re-ordering of equal elements, so you can't really call this change a breaking change.

Answer 3

As @Rawling said, have a look at the documentation for Sort():

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved.

So, you're trying to test something that is explicitly documented as undefined. That is not a breaking change.