Hacker News Reader

Comment by AstralStorm | Hacker News Reader

Oh my. Comparison sorts are still slower than counting sorts on typical architectures, esp. radix sort. (Coupled with insertion sort of small sizes.)

Or burstsort if the data size is truly huge.

As usual, StackOverflow is missing the forest for the trees.

View on HN

It's not even the fastest comparison-based sorter for the vast majority of inputs. There are much faster sorters out there that exploit the details of modern hardware (branch prediction is a big one, parallelism is also an obvious win if you can make use of it, etc), e.g. https://github.com/SaschaWitt/ips4o/ (sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort (sequential)

Well, nobody really uses plain quicksort in practice (maybe libc qsort?), but a lot of practical fast sort algorithms are variant (or based on) quicksort (including the ips4o you linked to if I'm reading the paper correctly).

A better claim would be that, among the comparison based sorts, algos in the quicksort family tend to be faster in practice.

Yeah, my implicit comparison was to something like std::sort from GNU's libstdc++, which is introsort, a quicksort-insertionsort-hybrid. Plain quicksort is indeed not great.

ips4o is a samplesort-derivative (the name stands for Inplace Super-Scalar Sample SOrt), which is kinda quicksort-derived, but doesn't use one pivot, but many (in the case of ips4o, 255, iirc). It's heritage traces back to quicksort, if you will, but it's also very different.

I enjoyed Alexandrescu’s CppCon 2019 talk “Speed Is Found In The Minds of People”

About optimizing generic sorting routines for modern hardware.

https://www.youtube.com/watch?v=FJJTYQYB1JQ

I remember learning in my college algorithms class that radix sort is 'slow in practice' because it's 'not cache friendly' then when we had a sorting speed competition project the fastest entry was a radix sort.

In principle, you can use radix sort for pretty much any real-world data. All you need is a canonical binary "sort key" representation, and you can implement MSD radix sort on top of that. (For variable-length data like strings, the sort key can be a lazy iterator in case you need to break ties for initially equal sort keys, which of course requires MSD not LSD radix sort.) Composite data types can just concatenate the sort keys of their members, recursively, much like we build hash code implementations. At some point I want to release a sorting library which introduces a new Rust trait for this purpose.

Can you elaborate on why bubble sort is fast on huge dataset?

Also, If counting based sorting algorithm is faster in practice , why we are not seeing more of it in database system?

That was burst sort, not bubble sort.

(That said, bubblesort can be fast if the data are usually very close to sorted - one example here is depth-sorting polygons for a rendering engine on a highly constrained platform.)

Another example application of adaptive sorts is the sweep-and-prune broadphase collision detection algorithm that's somewhat commonly used in physics engines.

Database systems do not operate on large strings and sort by keys rather than whole rows. And they tend to use hash maps as input invoking truly flat distributions. They also require sort stability.

Burstsort and radix sort are best for cases where you actually sort based on whole or almost whole structure comparison - as in memcmp.

Burstsort is also equivalent to walking a trie index in a database. So yes, you see it quite a lot.

What if all elements are unique?

Reply on news.ycombinator.com