Behaviour of List.Sort in .NET 4.5 changed from

问题:

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?

回答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.}

回答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.

回答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.

回答4:

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

回答5:

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.

回答6:

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.