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

26
votes

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?

6
c#.net.net-4.0.net-4.5
The spec still says it uses a QuickSort that may not preserve order. – Rawling
Although you're not the first to notice. (Also this mentions it being changed to an "introspective sort", which is not stable but is a different algorithm.) – Rawling
What might have happened is that QuickSort was modified in a way that makes this trivial sort appear stable. (Different choice of pivot maybe.) I'm not sure how to construct a test case that would conclusively prove whether the sorting algorithm in use is now stable or not, but comparing two elements isn't it. – millimoose
Another way to see if the difference is there is var li = new List<string> { "first", "second", }; li.Sort((x, y) => 0);. – Jeppe Stig Nielsen

6 Answers

36
votes

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 sort1, 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.

1By 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.

5
votes

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.

3
votes

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.

2
votes

I don't see any change. As others already wrote, both versions perform an unstable sort. Which means that you cannot rely on order of elements that compare as equals. Their order may or may not change during sort. It certainly isn't a breaking change.

See: Documentation of List< T >.Sort

1
votes

From MSDN

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

Doesn't look like the order is reliable therefore the test is void. Also, why are you testing the Sort method anyway? Seems like an unnecessary test to me.

0
votes

Questions like this often come up with new framework versions. There are some for the 3.5 → 4.0 transition here and here.

For this particular change of versions, the difference comes up already whith an array or List<> of two elements, as your question shows. Another simple example is:

using System;
using System.Linq;

namespace SortTest
{
  static class Program
  {
    static void Main()
    {
      var arr = new[] { new { Name = "Mary", Age = 17, }, new { Name = "Louise", Age = 17, }, };

      Array.Sort(arr, (x, y) => x.Age.CompareTo(y.Age));

      Console.WriteLine(string.Join(",", arr.Select(x => x.Name)));
    }
  }
}

With .NET 4.0 this prints Louise,Mary. The elements are swapped. However, with .NET 4.5 it prints Mary,Louise. Note that the two girls have the same age.

List<>.Sort instance method and Array.Sort static method are documented to be non-stable sorts. They are free to leave elements of equal "size" in any order they want. So your code must not make any assumptions about what order equivalent elements come in.

In contrast, Linq's OrderBy method performs a stable sort. So

var ordered = arr.OrderBy(x => x.Age);

is required to not swap Mary and Louise, given that they have the same Age.