Boost logo

Boost :

Subject: Re: [boost] Integer sorting
From: Robert Ramey (ramey_at_[hidden])
Date: 2019-01-20 19:14:10


On 1/20/19 10:11 AM, Marcin Copik via Boost wrote:
> 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?

It is very common knowledge that there are many sorting algorithms which
do not require O(n * log n) comparisons. In fact, there are many -
including the proposed integer sort - which do no comparisons at all.
It's very easy to find information on this. Just google radix sort,
postman's sort, among other search terms.

Robert Ramey
>
> Best,
> Marcin
>


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