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

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 2

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 3

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 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

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.