C# IComparer is returning unexpected result when comparing same strings

Question

I have a situation where all of my list members have same ID (Id is string and not Integer). As part of business rules I need to sort the list in ascending order. My original implementation is quite similar to below. I was expecting to get unchanged list after applying sort as all list members have same ID but to my surprise the result is different.

Below is my original list before Sort.

Id: D1.2 Name: Pachycephalosaurus
Id: D1.2 Name: Amargasaurus
Id: D1.2 Name: Mamenchisaurus
Id: D1.2 Name: Deinonychus
Id: D1.2 Name: Coelophysis
Id: D1.2 Name: Oviraptor
Id: D1.2 Name: Tyrannosaur

Sort with alternate comparer:

Id: D1.2 Name: Pachycephalosaurus
Id: D1.2 Name: Oviraptor
Id: D1.2 Name: Coelophysis
Id: D1.2 Name: Deinonychus
Id: D1.2 Name: Mamenchisaurus
Id: D1.2 Name: Amargasaurus
Id: D1.2 Name: Tyrannosaur

Code

class Program
{
    static void Main(string[] args)
    {
        new ComparerIssue().MainMethod();
        Console.ReadKey();
    }
}

internal class DinoComparer : IComparer<Dinosaur>
{
    public int Compare(Dinosaur dinosaur1, Dinosaur dinosaur2)
    {
        return Compare(dinosaur1.Id, dinosaur2.Id);
    }

    private int Compare(string x, string y)
    {
        if (x == y)
        {
            return 1; //I have tried using 1 and 0; -1 throws exception
        }
        return x.CompareTo(y);
    }
}
public class ComparerIssue
{
    public void MainMethod()
    {
        List<Dinosaur> dinosaurs = new List<Dinosaur>();
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Pachycephalosaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Amargasaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Mamenchisaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Deinonychus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Coelophysis" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Oviraptor" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Tyrannosaur" });
        Display(dinosaurs);

        DinoComparer dc = new DinoComparer();

        Console.WriteLine("\nSort with alternate comparer:");

        dinosaurs.Sort(dc);
        Display(dinosaurs);
    }
    private static void Display(IEnumerable<Dinosaur> list)
    {
        Console.WriteLine();
        foreach (Dinosaur dinosaur in list)
        {
            Console.WriteLine("Id: " + dinosaur.Id + " Name: " + dinosaur.Name);
        }
    }
}
public class Dinosaur
{
    public string Id { get; set; }
    public string Name { get; set; }
}

Answer 1

Sadly, as far as I know, there is no stable sort method implemented in Frameworks. You'll have to do it yourself.

This http://www.csharp411.com/c-stable-sort/ is a nice example of stable sort method.

Answer 2

You should return only return x.CompareTo(y); from your private int Compare(string x, string y) method, since you are comparing only based on strings...

Like this:

private int Compare(string x, string y)
{
    return x.CompareTo(y);
}

Hope it helps, Ivan

Answer 3

You're violating the implied contract of IComparer since, Compare(dino1,dino2) and Compare(dino2,dino1) will return that dino1 is greater than dino2 and dino2 is greater than dino1. Since you're not properly defining an order, the results will tend to be "random" at best.

If you can't define a total order based purely on the ID values, then just using the ID values can't be the basis for your IComparer implementation.

Answer 4

You're breaking the contract for IComparable; when your Ids are equal, you're actually saying one is greater than the other (so needs to be sorted)

From the documentation:

Less than zero This object is less than the other parameter. Zero This object is equal to other. Greater than zero This object is greater than other.

An alternate implementation for your Compare would be:

private int Compare(string x, string y)
{
    return x.CompareTo(y);
    // There would be potential to do secondary sorts if the line above only returned zero - you'd obviously need to capture and test the result...
}

Answer 5

Personally I would use the answer from icesar, but use the static string.Compare method instead:

return string.Compare(x, y);

This makes the compare a little "safer", you don't have to check for nulls.

Alternatively a simple LINQ statement will do the job:

myList = myList.OrderBy(p => p.ID).ThenBy(p => p.Name);

You should also note that sorting by ID as a string will lead to erroneous results once you get a few items in the list; 21 will be placed before 3. You may want to consider casting it to an int at some stage.

Answer 6

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.

(my emphasis)

Which is exactly what you see happen.

EDIT As hinted by others, you can use the linq method OrderBy, which does perform a stable sort:

var d2 = dinosaurs.OrderBy(d => d.Id).ToList();

Answer 7

I sincerely thanks everyone for the feedback. I have implemented stable sort using insertion method found at http://www.csharp411.com/c-stable-sort/. I am including the final code for reference.

internal class DinoComparer : IComparer<Dinosaur>
{
    public int Compare(Dinosaur dinosaur1, Dinosaur dinosaur2)
    {
        return Compare(dinosaur1.Id, dinosaur2.Id);
    }

    private int Compare(string x, string y)
    {
        return x.CompareTo(y);
    }
}
public class ComparerIssue
{
    public void MainMethod()
    {
        List<Dinosaur> dinosaurs = new List<Dinosaur>();
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Pachycephalosaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Amargasaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Mamenchisaurus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Deinonychus" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Coelophysis" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Oviraptor" });
        dinosaurs.Add(new Dinosaur() { Id = "D1.2", Name = "Tyrannosaur" });
        Display(dinosaurs);

        //Console.WriteLine("\nSort with unstable comparer:");
        //dinosaurs.Sort(new DinoComparer());

        Console.WriteLine("\nSort with stable comparer:");
        dinosaurs = (List<Dinosaur>)InsertionSort.Sort(dinosaurs, new DinoComparer().Compare);

        Display(dinosaurs);
    }
    private static void Display(IEnumerable<Dinosaur> list)
    {
        Console.WriteLine();
        foreach (Dinosaur dinosaur in list)
        {
            Console.WriteLine("Id: " + dinosaur.Id + " Name: " + dinosaur.Name);
        }
    }
}
public class Dinosaur
{
    public string Id { get; set; }
    public string Name { get; set; }
}
public class InsertionSort
{
    public static IList<T> Sort<T>(IList<T> list, Comparison<T> comparison)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        if (comparison == null)
            throw new ArgumentNullException("comparison");

        int count = list.Count;
        for (int j = 1; j < count; j++)
        {
            T key = list[j];

            int i = j - 1;
            for (; i >= 0 && comparison(list[i], key) > 0; i--)
            {
                list[i + 1] = list[i];
            }
            list[i + 1] = key;
        }
        return list;
    }
}