Faster than radix sort: Kirkpatrick-Reisch sorting
sortingsearching.com
Faster than radix sort: Kirkpatrick-Reisch sorting
1–10 of 47 posts
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#2> Faster
Benchmarks?
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#3> 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 implementation out there for it as well.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#4> Faster Benchmarks?
faster in the algorithmic rather than the performance sense
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#5I suspect memory indirection would clobber the theoretical perf, but I'd be happy to be proved wrong.
My inclination is that this would be slower than "standard" high perf radix sorting, but I'm not sure if the high level overview of this algorithm represents an equivalent level of implementation.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#6> 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…
vvanders, I believe you’ve worked in games so you might already know about how the PlayStation 1 kindof had radix sort baked into the hardware. The hardware had no Z buffer, so all polygons had to be ordered back-to-front using the Painter’s Algorithm for visibility. The hardware understood a linked list of polygons; as odd as that sounds. And, the standard practice presented by the API was to have a pre-allocated linear array of NOP list nodes forming a radix as the starting point for inserting sorted polys.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#7> Faster Benchmarks?
faster in the algorithmic rather than the performance sense
That's not what "faster" means. Computational complexity means expected asymptotic behaviour followig certain assumptions. More often than not don't happen in the real world, or don't take in consideration real-world properties such as tiered cache and the impact of cache misses.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#8> Faster Benchmarks?
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 probabilistically but not deterministically true)
That said, word size w is, in almost all integer dieting problems, bounded by 128 (by 64 or even 32 with high probability) which makes it acceptable to regard as “constant” in which case both sorts are essentially O(n) and it all depends on specific implementations (with radix sort likely significantly faster in practice)
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#9> 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 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.
Re: Faster than radix sort: Kirkpatrick-Reisch sorting
#10> Faster Benchmarks?
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...