Re: [boost] Integer sorting

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
>