Order of List using Linq is not the same as sort

Question

I would like to confirm this, I was trying to sort a List of my class using Linq. But it seems the order of the data was not ordering the same way when i used a sort function.

Assume that the list contains 4 ComputeItem and all their A are set to 1, the B, C, D of all are set to zero.

CASE 1:

ItemList =
    ItemList
        .OrderByDescending(m => m.A)
        .ThenBy(m => m.B)
        .ThenBy(m => m.C)
        .ThenBy(m => m.D)
        .ToList<ComputeItem>();

versus

CASE 2:

ItemList.Sort(
    delegate(ComputeItem item1, ComputeItem item2)
    {
        if (item1.A == item2.A)
        {
            if (item1.B == item2.B)
            {
                if (item1.C == item2.C)
                {
                    return item1.D - item2.D;
                }
                else
                {
                    return item1.C - item2.C;
                }
            }
            else
            {
                return item1.B - item2.B;
            }
        }
        else
        {
            return item2.A - item1.A;
        }
    }
);

The result of the first sort is it did not move anything.
The result of the second sort is it sorted it to a different order.
Orignial Order [1, 2, 3, 4]
CASE 1 new Order [1, 2, 3, 4]
CASE 2 new Order [3, 4, 1, 2]

Now the problem is before I was using CASE2 and am trying to migrate it to CASE 1. But the behavior cannot change drastically than before. Any idea why the CASE 2 moved the ordering?

Answer 1

The sorting algorithm used by OrderBy, OrderByDescending, ThenBy, and ThenByDescending is a stable QuickSort. From the MSDN documentation:

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved.

List<T>.Sort uses an unstable version of QuickSort, which does not necessarily preserve the original ordering of equal elements. Again, from the MSDN documentation:

This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved.

This explains the discrepancy you are seeing. Obviously, the end result of both will be that the items are ordered in the manner dictated by your comparison mechanism. It's only the order in which equal elements appear that is unspecified for List<T>.Sort.

The good news is that you're going from an unstable sort to a stable sort. I have trouble imagining that this could be a breaking change for you (what kind of software requires that a sort be unstable?). If anything it should make your program that much more predictable.