4 ms·
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
by vvanders 6y ago
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.
- moonchild 6y ago> 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.
- corysama 6y agovvanders, 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.
- beagle3 6y ago> 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.