Re: [boost] Integer sorting

Subject: Re: [boost] Integer sorting
From: Marcin Copik (mcopik_at_[hidden])
Date: 2019-01-20 18:11:46

Fenil,

niedz., 20 sty 2019 o 18:22 użytkownik Fenil Mehta via Boost <
boost_at_[hidden]> 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 <boost_at_[hidden]>
> wrote:
>
> > On Sat, 29 Dec 2018 at 11:16, degski <degski_at_[hidden]> 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
>