Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk