O(n+n * log(w/log(n)) )
Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
Faster than radix sort: Kirkpatrick-Reisch sorting
11–20 of 47 posts
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#12O(n+n * log(w/log(n)) ) Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
Not sure whether it applies here, but _if_ n is the number of unique values, you are limited here by the fact that there are only 2^w unique integers. Hence n < 2^w
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#13O(n+n * log(w/log(n)) ) Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
The recursion assumes that log(n) > w; if log(n) <= w, then you're in the base case and it's O(n).
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#14O(n+n * log(w/log(n)) ) Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
Not sure what's going on here, but that does indeed seem to be the case: https://www.wolframalpha.com/input/?i=x%2Bx+*+log%282%2Flog%...
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#15Written by Tomek Czajka, a 3x TopCoder winner and algorithmic mastermind. Worth following!
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#16Written by Tomek Czajka, a 3x TopCoder winner and algorithmic mastermind. Worth following!
And he's a spaceX engineer
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#17O(n+n * log(w/log(n)) ) Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
The algorithm is to switch to a counting sort when w = 2^w, so more properly the complexity is written:
O(n+max(0,log(w/log n)))Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#18If you are into integer sorting, this might be of interest as well:
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#19> Faster Benchmarks?
Yeah, would be curious as well. There's two really awesome things about radix sort: 1. It scans in linear order, so if you tune your radix size to L1/L2 cache it will happily beat other "faster" algorithms thanks to the prefetcher. 2. If preserves ordering for keys with the same value. #2 makes is a really good depth-sorting algorithm for alpha rendering, and #1 just makes it darn fast. There's a nice floating point…
> It preserves ordering for keys with the same value
That's called a stable sort, and it's a standard property present in many sorting algorithms.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#20Earlier quoted context omitted.
In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistica…
Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...
Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.