Re: [boost] Integer sorting

Subject: Re: [boost] Integer sorting
From: Jack Adrian Zappa (adrianh.bsc_at_[hidden])
Date: 2019-01-20 18:08:48

On Sun, Jan 20, 2019 at 12:22 PM Fenil Mehta via Boost
<boost_at_[hidden]> wrote:
>
> Hi,
>
> I am Fenil Mehta, a 3rd year Computer Science and Engineering student.
>
> In response to the past suggestions I have added the comparison graphs of
> ir_sort::integer_sort for different size of integers and various array
> lengths with various sorting algorithms of boost to my GitHub[1].
> I have also added the explanation of basic working to my GitHub[1]
>
> For arrays of large objects, I have made an improvement which is more
> efficient as compared to any sorting algorithm I have ever tried (including
> ska_sort, std::sort, boost::sort::spreadsort::integer_sort,
> boost::sort::pdqsort, boost::sort::spinsort,
> boost::sort::flat_stable_sort). It is about two times faster than ska_sort,
> spreadsort, pdqsort and five times faster than std::sort, spinsort,
> flat_stable_sort.
>
> From my knowledge and the learning's of past six months by working on this
> sorting project(ir_sort), I have few more optimizations in mind which would
> improve the sorting speed even more.
>
> I would like to contribute to this organization in view of GSoC(Google
> Summer of Code) 2019. It would be great if someone could mentor me
> regarding the improved sorting algorithm that I have written in C++14.
>
> [1] GitHub link: https://github.com/fenilgmehta/Fastest-Integer-Sort
>
> 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

Your numbers are impressive, but how can you have a sort algorithm
that is O(n) complexity?  I know that I could go and analyse your
code, but it would be easier if you just explained it.

Adrian