Why does .NET 4.0 sort this array differently than .NET 3.5?

Question

In this stackoverflow question, an interesting question arose about sorting double arrays with NaN values. The OP posted the following code:

static void Main(string[] args) { double[] someArray = { 4.0, 2.0, double.NaN, 1.0, 5.0, 3.0, double.NaN, 10.0, 9.0, 8.0 }; foreach (double db in someArray) { Console.WriteLine(db); } Array.Sort(someArray); Console.WriteLine("\n\n"); foreach (double db in someArray) { Console.WriteLine(db); } Console.ReadLine(); } 

When you run it under the .NET 3.5 platform, the array is sorted as follows:

1,4,NaN,2,3,5,8,9,10,NaN

When you run it under .NET 4.0, the array is sorted somewhat more logically:

NaN,NaN,1,2,3,4,5,8,9,10

I can understand why it will sort weird in .NET 3.5 (because NaN is not equal, less or more than anything). I can also understand why it will sort it the way it is done in .NET 4.0. My question is: why did this change from 3.5 to 4.0? And where is the Microsoft documentation for this change?

Answer 1

This is a bug fix. A feedback report with error details is here . Microsoft's answer to the error report:

Please note that this error affects the following:

• Array.Sort (), where the array contains Double.NaN
• Array.Sort (), where the array contains Single.NaN
• all callers, for example, in List.Sort (), where the list contains Double.NaN

This bug will be fixed in the next major version of the runtime; until then, you can get around this using a special IComparer that does the right sort. As mentioned in the workaround comments, do not use Comparer.Default, because it is specifically using a shortcut sorting procedure that does not properly handle NaN. Instead, you can provide your own comparer, which provides an equivalent comparison, but will not be specially taxed.

Answer 2

Not quite an answer, but perhaps a hint ... You can reproduce the strange behavior of 3.5 in 4.0 with this code:

 void Main() { double[] someArray = { 4.0, 2.0, double.NaN, 1.0, 5.0, 3.0, double.NaN, 10.0, 9.0, 8.0 }; Array.Sort(someArray, CompareDouble); someArray.Dump(); } int CompareDouble(double a, double b) { if (a > b) return 1; if (a < b) return -1; return 0; } 

Here, both a > b and a < b return false if a or b is NaN , so the CompareDouble method returns 0, so NaN is considered equal to all ... This gives the same result as in 3.5:

 1,4,NaN,2,3,5,8,9,10,NaN 

Answer 3

I don't have code for the .NET 3.5 runtime to check this out, but I think they fixed the error in the standard comparator for double to bring it into line with the documentation .

According to this document, Double.Compare treats NaN as equal to PositiveInfinity and NegativeInfinity and less than any other value.

The documentation is the same for .NET 3.5 and .NET 4.0, so I should think that this was a bug fix so that the code works as documented.

EDIT:

After reading the comments in a related question, I should think that the problem is not Double.Compare , but that it uses the Array.Sort method (on which List.Sort depends) to compare the double value. Anyway, I don’t think this is really Double.Compare .

Answer 4

[This is my answer, shameless, torn from another post. It would be nice if someone double.CompareTo this further - double.CompareTo and double.CompareTo(double) clearly defined as below, so I suspect there is some kind of Array.Sort magic for a certain type.]

Array.Sort(double[]) : it seems that CompareTo(double[]) is not used, and this can be a very mistake - note the difference in Array.Sort (object []) and Array.Sort (double []) below. I would like to clarify / fix the following:

Firstly, double.CompareTo(T) documentation - this ordering is clearly defined in accordance with the documentation :

Less than zero: This instance is less than the value. -or- This instance is not a number (NaN), but the value is a number.

Zero This instance is equal to the value. -or- And this instance and value are not a number (NaN), PositiveInfinity or NegativeInfinity.

Greater than zero: This instance is greater than the value. -or- This instance is a number and a value, not a number (NaN).

In LINQPad (3.5 and 4 both have the same results):

 0d.CompareTo(0d).Dump(); // 0 double.NaN.CompareTo(0d).Dump(); // -1 double.NaN.CompareTo(double.NaN).Dump(); // 0 0d.CompareTo(double.NaN).Dump(); // 1 

Using CompareTo(object) has the same results:

 0d.CompareTo((object)0d).Dump(); // 0 double.NaN.CompareTo((object)0d).Dump(); // -1 double.NaN.CompareTo((object)double.NaN).Dump(); // 0 0d.CompareTo((object)double.NaN).Dump(); // 1 

So no problem.

Now from Array.Sort(object[]) documentation is not used > , < or == (according to the documentation) is just CompareTo(object) .

Sorts the elements in the entire one-dimensional array using the IComparable implementation of each element of the array.

Similarly, Array.Sort(T[]) uses CompareTo(T) .

Sorts the elements in the entire array using the implementation of the universal IComparable (Of T) interface of each element of the array.

We'll see:

LINQPad (4):

 var ar = new double[] {double.NaN, 0, 1, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, NaN, 0, 1 

LINQPad (3.5):

 var ar = new double[] {double.NaN, 0, 1, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, 0, NaN, 1 

LINQPad (3.5) - NOTE. ARRAY IS OBJECT , and the behavior is "expected" in the CompareTo contract.

 var ar = new object[] {double.NaN, 0d, 1d, double.NaN}; Array.Sort(ar); ar.Dump(); // NaN, NaN, 0, 1 

Hm. Indeed. Finally:

I HAVE NOT AN IDEA - but I suspect that there is some "optimization", as a result of which CompareTo(double) not called.

Happy coding.