List<T>.Sort sorting nulls incorrectly

Question

I have a list of objects, some of which can be null. I want it sorted by some property, with nulls at the end of list. However, List<T>.Sort() method seems to put nulls in the beginning no matter what the comparer returns. This is a little program that I used to test this:

class Program
 {
  class Foo {
   public int Bar;
   public Foo(int bar)
   {
    Bar = bar;
   }
  }
  static void Main(string[] args)
  {
   List<Foo> list = new List<Foo>{null, new Foo(1), new Foo(3), null, new Foo(100)};

   foreach (var foo in list)
   {
     Console.WriteLine("Foo: {0}", foo==null?"NULL":foo.Bar.ToString());
   }

   Console.WriteLine("Sorting:");
   list.Sort(new Comparer());
   foreach (var foo in list)
   {
    Console.WriteLine("Foo: {0}", foo == null ? "NULL" : foo.Bar.ToString());
   }
   Console.ReadKey();
  }
  class Comparer:IComparer<Foo>
  {
   #region Implementation of IComparer<in Foo>

   public int Compare(Foo x, Foo y)
   {
    int xbar = x == null ? int.MinValue : x.Bar;
    int ybar = y == null ? int.MinValue : y.Bar;
    return ybar - xbar;
   }

   #endregion
  }
 }

Try this yourself: sorted list is printed as

Foo: NULL
Foo: NULL
Foo: 100
Foo: 3
Foo: 1

nulls Are first, even though they're compared as int.Minvalue. Is the method buggy or what?

Answer 1

Let’s say x is null and y is 1.

int xbar = x == null ? int.MinValue : x.Bar;
int ybar = y == null ? int.MinValue : y.Bar;
return ybar - xbar;

So now we have 1 - int.MinValue. This will be an overflow, so the end result will be negative, hence the null will be considered less than 1.

For that reason, the computation is fundamentally flawed.

public int Compare(Foo x, Foo y)
{
    int xbar = x == null ? int.MinValue : x.Bar;
    int ybar = y == null ? int.MinValue : y.Bar;
    return ybar.CompareTo(xbar);
}

(Thanks to the commenters for pointing out the flaw in my method.)

Answer 2

int.MinValue is -2147483648.

Now, suppose you were comparing 3 and -2147483648 via subtraction, specifically 3 - (-2147483648?

Also you should consider using the null coalescing operator ??

Answer 3

Your implementation of IComparer.Compare is unnecessarily complex. Remember that all that matters about the return value is the sign - the magnitude is unimportant. To have nulls compare less than all real Foos, simply defer to Int32s implementation of CompareTo, after making your substitution:

return       (x == null ? int.MinValue : x.Bar)
  .CompareTo((y == null ? int.MinValue : y.Bar))

Answer 4

Replace this line:

return ybar - xbar;

with this line:

return ybar.CompareTo(xbar);

Because your arithmetic is overflowing.

Answer 5

Your implementation is incorrect because you failed to write the specification first, then write code that meets the specification.

So, start over. Write a specification:

• FooCompare takes two references to Foo, x and y. Either may be null.
• IComparer.Compare(x,y) is documented as returning zero if x and y are equal, negative if y is greater than x, and positive if y is smaller than x. We will follow this convention.
• if x and y are both null, they are equal.
• if one is null and the other one is not then the null one is the smaller.
• if neither are null then the comparison is based on the value of the Bar property.

And now you can write code that you are guaranteed matches the spec:

// FooCompare takes two references to Foo, x and y. Either may be null.
// +1 means x is larger, -1 means y is larger, 0 means they are the same.

int FooCompare(Foo x, Foo y)
{
    // if x and y are both null, they are equal.
    if (x == null && y == null) return 0;
    // if one is null and the other one is not then the non-null one is larger.
    if (x != null && y == null) return 1; 
    if (y != null && x == null) return -1; 
    // if neither are null then the comparison is 
    // based on the value of the Bar property.
    var xbar = x.Bar; // only calculate x.Bar once
    var ybar = y.Bar; // only calculate y.Bar once
    if (xbar > ybar) return 1;
    if (ybar > xbar) return -1;
    return 0;
}

// The original poster evidently wishes the list to be sorted from
// largest to smallest, where null is the smallest.
// Reverse the polarity of the neutron flow:
int Compare(Foo x, Foo y)
{
    return FooCompare(y, x);
}

Don't mess around with clever integer arithmetic tricks; as you've seen, clever equals buggy. Correctness first.