List.Sort in C#: comparer being called with null object

Question

I am getting strange behaviour using the built-in C# List.Sort function with a custom comparer.

For some reason it sometimes calls the comparer class's Compare method with a null object as one of the parameters. But if I check the list with the debugger there are no null objects in the collection.

My comparer class looks like this:

public class DelegateToComparer<T> : IComparer<T> {     private readonly Func<T,T,int> _comparer;      public int Compare(T x, T y)     {         return _comparer(x, y);     }      public DelegateToComparer(Func<T, T, int> comparer)     {         _comparer = comparer;     } } 

This allows a delegate to be passed to the List.Sort method, like this:

mylist.Sort(new DelegateToComparer<MyClass>(     (x, y) => {           return x.SomeProp.CompareTo(y.SomeProp);       }); 

So the above delegate will throw a null reference exception for the x parameter, even though no elements of mylist are null.

UPDATE: Yes I am absolutely sure that it is parameter x throwing the null reference exception!

UPDATE: Instead of using the framework's List.Sort method, I tried a custom sort method (i.e. new BubbleSort().Sort(mylist)) and the problem went away. As I suspected, the List.Sort method passes null to the comparer for some reason.

Answer 1

This problem will occur when the comparison function is not consistent, such that x < y does not always imply y < x. In your example, you should check how two instances of the type of SomeProp are being compared.

Here's an example that reproduces the problem. Here, it's caused by the pathological compare function "compareStrings". It's dependent on the initial state of the list: if you change the initial order to "C","B","A", then there is no exception.

I wouldn't call this a bug in the Sort function - it's simply a requirement that the comparison function is consistent.

using System.Collections.Generic;  class Program {     static void Main()     {         var letters = new List<string>{"B","C","A"};          letters.Sort(CompareStrings);     }      private static int CompareStrings(string l, string r)     {         if (l == "B")             return -1;          return l.CompareTo(r);     } }