0

I ran into a problem with IComparer and System.Collections.Generic.List when all items are considered equal:

If all items in the source list are considered equal, I would expect the "sorted" list to have exactly the same item order than the source list (i.e. remain unchanged).

However, I noticed that the item order in the sorted list is different.

For example, imagine I sort a list of person objects by first name:

Source list:

  1. John Miller
  2. John Smith
  3. John Doe
  4. John Williams

Result comparing the first name with IComparer:

    1. John Williams
    1. John Smith
    1. John Miller
    1. John Doe

To reproduce:

public class AllTheSameComparer : IComparer<int>
{
    public int Compare(int x, int y)
    {
        return 0; // all are equal
    }
}

The following unit test will fail for more than 20 items:

    [TestMethod]
    public void testCompareSimple()
    {
        var numbers = new List<int>();

        for (var i = 0; i < 2000; i++)
        {
            numbers.Add(i);
        }

        var fixture = new AllTheSameComparer();

        numbers.Sort(fixture);

        for (var i = 0; i < numbers.Count; i++)
        {
            var actual = numbers[i];
            Assert.AreEqual(i, actual);
        }

    }

Is this expected behavior? Is there a way for me to keep the original item order of equal elements without having to compare a second object property?

Mark
  • 6,647
  • 1
  • 45
  • 88
  • 3
    This is expected behaviour. From [the docs](https://msdn.microsoft.com/en-us/library/w56d4y5z(v=vs.110).aspx): `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.` – RB. Jun 16 '16 at 10:58
  • 3
    [`List.Sort`](https://msdn.microsoft.com/en-us/library/234b841s(v=vs.110).aspx) _performs an unstable sort_. You could use LINQ's `...OrderBy(...).ToList()`. You can even use your `IComparer` in [`Enumerable.OrderBy`](https://msdn.microsoft.com/en-us/library/bb549422(v=vs.110).aspx). – Tim Schmelter Jun 16 '16 at 10:59
  • See [Stability in sorting algorithms](http://stackoverflow.com/questions/1517793/stability-in-sorting-algorithms) – Liam Jun 16 '16 at 11:15

0 Answers0