Re:Faster than radix sort: Kirkpatrick-Reisch sorting
by beagle3 on Tuesday June 09, 2020 @02:33AM
(#23464282)
> it will happily beat other "faster" algorithms
When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable.
It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.
When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable.
It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.