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:
> 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, gregod at, cpdaniel at, john at