Sorting floating-point values, and NaN

[tn]

On Tuesday, 12 November 2013 at 07:33:57 UTC, qznc wrote:
> On Tuesday, 12 November 2013 at 04:41:56 UTC, Vladimir 
> Panteleev wrote:
>> double[] arr = [1, 2, 3, double.nan, 1, 2];
>> assert(arr.isSorted);
>> arr.sort();
>>
>> This code will fail with an assert error, but not the one on 
>> the second line. Rather, it will fail inside std.range, when 
>> sort calls assumeSorted, which checks elements in an order 
>> different than sort and isSorted.
>>
>> Here's a case where the odd way NaN interacts with generic 
>> code messes things up in an ugly way.
>>
>> This is concerning. It's very easy to overlook this while 
>> writing an application, and it can become a hidden 
>> vulnerability.
>>
>> We can't fix the operators... but, perhaps, we could define a 
>> safe default comparison predicate (e.g. std.algorithm.less) 
>> for use with sorting and related tasks? Aside from bitwise 
>> comparison, is it even possible to efficiently compare 
>> floating-point values in a way suitable for sorting?
>
> You cannot sort NaNs. A comparison with NaN must always 
> evaluate to false.
>
> One could change isSorted to check for false instead of true, 
> so it would accept NaN. That would probably break too much 
> code, though.
>
>   arr[n] < arr[n+1]  => !(arr[n+1] < arr[n])

But that is exactly what it does.

https://github.com/D-Programming-Language/phobos/blob/8372da44f66f20c67b69b4b8fb39233ce42d493c/std/algorithm.d#L10021

And that is the reason the second line "assert(arr.isSorted);" 
passes, while it should fail as the array is clearly not sorted. 
Instead modifying

   !(arr[n+1] < arr[n])  =>  arr[n] <= arr[n+1]

would make the function work correctly (return false if the range 
contains nans), but then the template parameter "less" should be 
replaced by "lessOrEqual". An alternative would be to check for 
nans explicitly.