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

Are you sure the problem isn't that SomeProp is null?

In particular, with strings or Nullable<T> values.

With strings, it would be better to use:

list.Sort((x, y) => string.Compare(x.SomeProp, y.SomeProp));

(edit)

For a null-safe wrapper, you can use Comparer<T>.Default - for example, to sort a list by a property:

using System;
using System.Collections.Generic;
public static class ListExt {
    public static void Sort<TSource, TValue>(
            this List<TSource> list,
            Func<TSource, TValue> selector) {
        if (list == null) throw new ArgumentNullException("list");
        if (selector == null) throw new ArgumentNullException("selector");
        var comparer = Comparer<TValue>.Default;
        list.Sort((x,y) => comparer.Compare(selector(x), selector(y)));
    }
}
class SomeType {
    public override string ToString() { return SomeProp; }
    public string SomeProp { get; set; }
    static void Main() {
        var list = new List<SomeType> {
            new SomeType { SomeProp = "def"},
            new SomeType { SomeProp = null},
            new SomeType { SomeProp = "abc"},
            new SomeType { SomeProp = "ghi"},
        };
        list.Sort(x => x.SomeProp);
        list.ForEach(Console.WriteLine);
    }
}

Answer 2

Marc's answer is useful. I agree with him that the NullReference is due to calling CompareTo on a null property. Without needing an extension class, you can do:

mylist.Sort((x, y) => 
      (Comparer<SomePropType>.Default.Compare(x.SomeProp, y.SomeProp)));

where SomePropType is the type of SomeProp

Answer 3

For debugging purposes, you want your method to be null-safe. (or at least, catch the null-ref. exception, and handle it in some hard-coded way). Then, use the debugger to watch what other values get compared, in what order, and which calls succeed or fail.

Then you will find your answer, and you can then remove the null-safety.

Answer 4

Can you run this code ...

mylst.Sort((i, j) =>
              {
                  Debug.Assert(i.SomeProp != null && j.SomeProp != null);
                  return i.SomeProp.CompareTo(j.SomeProp);
              }
         );

Answer 5

I stumbled across this issue myself, and found that it was related to a NaN property in my input. Here's a minimal test case that should produce the exception:

public class C {

    double v;

    public static void Main() {
        var test =
            new List<C> { new C { v = 0d },
                          new C { v = Double.NaN },
                          new C { v = 1d } };
        test.Sort((d1, d2) => (int)(d1.v - d2.v));
    }

}

Answer 6

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);
    }
}

Answer 7

Hi, I am getting the same error.

1. I am using single thread.
2. All the values in the array being sorted are non null (Checking all just before sorting).
3. Area() function does return a valid float value every item (Checking all just before sorting).

static int CompareLoops(Polygon2 x, Polygon2 y) { float l1 = x.Area(); float l2 = y.Area(); if (l1 > l2) return 1; if (l1 == l2) return 0; return -1; }

Any ideas?

Answer 8

The same problem appears here - null checking in collection before calling Sort(), and crashing in Compare() with a null object - and I think Lee's answer will be the correct in my case. Thanks Lee!