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:
> niedz., 20 sty 2019 o 18:22 uÅ¼ytkownik Fenil Mehta via Boost <
> boost_at_[hidden]> napisaÅ:
>>  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.