Sorting floating-point values, and NaN

[tn]

On Tuesday, 12 November 2013 at 21:07:48 UTC, Andrei Alexandrescu 
wrote:
> On 11/12/13 1:03 PM, tn wrote:
>> On Tuesday, 12 November 2013 at 20:03:37 UTC, Andrei 
>> Alexandrescu wrote:
>>> Consider we define equiv(a, b) as (a, b) => !less(a, b) && 
>>> !less(b, a).
>>>
>>> If at least one of the numbers is NaN, all comparisons return 
>>> false.
>>> That puts NaN in the same equivalence class with all numbers,
>>> including numbers that are deemed in distinct equivalence 
>>> classes.
>>> That's where NaNs mess things up, and that's what we need to 
>>> assert.
>>> Consider three numbers a, b, and c. Then the following must 
>>> pass:
>>>
>>> assert((equiv(a, b) && equiv(b, c)) <= equiv(a, c));
>>>
>>> ("<=" on Booleans is actually implication.)
>>
>> Shouldn't the implication be to the other direction? Then it 
>> becomes
>>
>> assert((equiv(a, b) && equiv(b, c)) => equiv(a, c));
>
> It is in the other direction, but the latter doesn't compile 
> :o). Again, it just turns out "a <= b" has the meaning of "a 
> implies b". It's not a particularly intuitive way to express it.
>
>>> That test will fail with NaNs and should be part of isSorted, 
>>> sort etc.
>>
>> But it requires that the input contains at least three 
>> elements. And it
>> has to test a lot of possible triples (a,b,c), which I think 
>> requires at
>> least O(n^2) time. And it does not fail consistently whenever 
>> the input
>> contains at least one NaN (consider an input that contains 
>> only NaNs).
>
> I agree. Ideas?

If you want the isSorted function to always fail if the input 
contains NaNs, then I have no other ideas than what I have 
already mentioned. It is just not possible by using only "<" 
comparison. Something more is needed.

The other way would be to define isSorted to return true if and 
only if the _comparable_ elements in the input are sorted (thus 
ignoring possible NaNs in between). This is actually 
implementable with only "<" comparison, but probably requires 
O(n^2) time in the worst case.