Why does List<T>.Sort method reorder equal IComparable<T> elements?

Question

I have a problem with how the List Sort method deals with sorting. Given the following element:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        return Priority.CompareTo(other.Priority);
    }
}

If I try to sort it this way:

List<Element> elements = new List<Element>()
                             {
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "First"
                                     },
                                 new Element()
                                     {
                                         Priority = 1,
                                         Description = "Second"
                                     },
                                 new Element()
                                     {
                                         Priority = 2,
                                         Description = "Third"
                                     }
                             };
elements.Sort();

Then the first element is the previously second element "Second". Or, in other words, this assertion fails:

Assert.AreEqual("First", elements[0].Description);

Why is .NET reordering my list when the elements are essentially the same? I'd like for it to only reorder the list if the comparison returns a non-zero value.

Answer 1

From the documentation of the List.Sort() method from MSDN:

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. In contrast, a stable sort preserves the order of elements that are equal.

Here's the link: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Essentially, the sort is performing as designed and documented.

Answer 2

Here is an extension method SortStable() for List<T> where T : IComparable<T>:

public static void SortStable<T>(this List<T> list) where T : IComparable<T>
{
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList();
    list.Clear();
    list.AddRange(listStableOrdered);
}

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return x.CompareTo(y);
    }
}

Test:

[Test]
public void SortStable()
{
    var list = new List<SortItem>
                    {
                        new SortItem{ SortOrder = 1, Name = "Name1"},
                        new SortItem{ SortOrder = 2, Name = "Name2"},
                        new SortItem{ SortOrder = 2, Name = "Name3"},
                    };

    list.SortStable();

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1));
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1"));
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2"));
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2));
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3"));
}

private class SortItem : IComparable<SortItem>
{
    public int SortOrder { get; set; }
    public string Name { get; set; }

    public int CompareTo(SortItem other)
    {
        return SortOrder.CompareTo(other.SortOrder);
    }
}

In the test method, if you call Sort() method instead of SortStable(), you can see that the test would fail.

Answer 3

You told it how to compare things and it did. You should not rely on internal implementation of Sort in your application. That's why it let's you override CompareTo. If you want to have a secondary sort parameter ("description" in this case), code it into your CompareTo. Relying on how Sort just happens to work is a great way to code in a bug that is very difficult to find.

You could find a stable quicksort for .NET or use a merge sort (which is already stable).

Answer 4

See the other responses for why List.Sort() is unstable. If you need a stable sort and are using .NET 3.5, try Enumerable.OrderBy() (LINQ).

Answer 5

You can fix this by adding an "index value" to your structure, and including that in the CompareTo method when Priority.CompareTo returns 0. You would then need to initialize the "index" value before doing the sort.

The CompareTo method would look like this:

public int CompareTo(Element other)
{
    var ret = Priority.CompareTo(other.Priority);
    if (ret == 0)
    {
        ret = Comparer<int>.Default.Compare(Index, other.Index);
    }
    return ret;
}

Then instead of doing elements.Sort(), you would do:

for(int i = 0; i < elements.Count; ++i)
{
    elements[i].Index = i;
}
elements.Sort();

Answer 6

In some applications, when a list of items is sorted according to some criterion, preserving the original order of items which compare equal is unnecessary. In other applications, it is necessary. Sort methods which preserve the arrangement of items with matching keys (called "stable sorts" are generally either much slower than those which do not ("unstable sorts"), or else they require a significant amount of temporary storage (and are still somewhat slower). The first "standard library" sort routine to become widespread was probably the qsort() function included in the standard C library. That library would frequently have been used to sort lists that were large relative to the total amount of memory available. The library would have been much less useful if it had required an amount of temporary storage proportional to the number of items in the array to be sorted.

Sort methods that will be used under frameworks like Java or .net could practically make use of much more temporary storage than would have been acceptable in a C qsort() routine. A temporary memory requirement equal to the size of the array to be sorted would in most cases not pose any particular problem. Nonetheless, since it's been traditional for libraries to supply a Quicksort implementation, that seems to be the pattern followed by .net.

Answer 7

If you wanted to sort based on two fields instead of one you could do this:

class Element : IComparable<Element>
{
    public int Priority { get; set; }
    public string Description { get; set; }

    public int CompareTo(Element other)
    {
        if (Priority.CompareTo(other.Priority) == 0)
        {
            return Description.CompareTo(other.Description);
        } else {
            return Priority.CompareTo(other.Priority);
        }
    }
}

Obviously, this doesn't satisfy the requirement of a stable search algorithm; However, it does satisfy your assertion, and allows control of your element order in the event of equality.