Re: [boost] Integer sorting

Fenil, niedz., 20 sty 2019 o 18:22 użytkownik Fenil Mehta via Boost < boost@lists.boost.org> napisał:

[1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort

Would you care to explain how you algorithm sorts in a linear number of comparisons as you claim in the repository description? Isn't it the case that you have to perform at least O(n * logn) comparisons? Best, Marcin

Regards, Fenil Mehta

On Sat, Dec 29, 2018 at 2:59 PM degski via Boost wrote:

...

On Sat, 29 Dec 2018 at 11:16, degski wrote:

...

It would be useful to benchmark against ska_sort[1] as well [in addition to the Boost implementation], which I would say is the fastest (radix-)sort around [and simple to use].

Some write-up on "how it works"[2]

degski [1] https://github.com/skarupke/ska_sort [2] https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/ -- *“If something cannot go on forever, it will stop" - Herbert Stein*

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost