Sorting floating-point values, and NaN

[monarch_dodra]

On Tuesday, 12 November 2013 at 22:17:10 UTC, Vladimir Panteleev
wrote:
> On Tuesday, 12 November 2013 at 21:15:39 UTC, Andrei 
> Alexandrescu wrote:
>> We can make that work if we insert the tests at the end of a 
>> run of equivalent values.
>
> I've thought about this as well, but then there are cases 
> like...
>
> [4, 5, NaN, 3, NaN, 5, 6]
>
> "5, NaN, 3, NaN, 5" is a run of equivalent values as long as 
> neighboring pairs are concerned.
>
>> The point here is that we should work together on an 
>> innovative solution. Getting bogged in the "there's a problem 
>> with the language here" mindset prevents the forming of good 
>> ideas.
>
> Agreed.

I may be late to the party, but I think it might be a bit unfair
for sort to be able to reliably "catch" this issue.

Heck, if you call *sort* with NaN, how should it even behave?
Error? Exception?

With AssumeSorted, I think it should throw an Error, if it can
*reliably* do so.

--------

That said, we may have been looking at this problem the wrong
way. Instead of trying to verify the comparison inside the sort,
why not do the check in the comparator itself? It is the
comparator that should "know" how to deal with NaN: Either it
considers it bigger/smaller than everything, and sorts
accordingly, or doesn't know how to deal with it, and throws an
Error/Exception, depending on the users' wishes.

We could make sort/assumeSorted default comparator simply assert
on NaN: This should be able to keep the handling of the NaN
relatively customizable, and cheap in release, without having to
hack into sort/assumeSorted, to do some weird bidirectional
checks.

This keeps the default fast and safe, and if users want more
speed/customization, they can do whatever the heck they like.

My 0.02$