Sorting floating-point values, and NaN

[tn]

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

> 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).

> We should also check such as:
>
> assert(!less(a, a));
> assert(less(a, b) <= !less(b, a));
>
> These should be checked in sort only; isSorted does not need 
> these.

The latter fails also if a==b. (Unless the direction of the 
implication is again wrong.)