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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk