Hacker News Reader

Comment by dehrmann | Hacker News Reader

With how long we've been studying sorting algorithms, I'm amazed we're still coming up with optimizations that yield real-world improvements.

View on HN

It's not just the algorithms, but the hardware as well; the base algorithms we were taught in school were usually aimed at single-threaded applications, but in the past two decades, multithreading and parallelisation has become mainstream.

That's not particularly relevant, no standard library sort method is using multithreading in the background. It actually is about algorithmic improvements.

For sorting algorithms many of the "algorithmic improvements" are caching / locality / access pattern improvements, as latency differences get more extreme and cache sizes grow. (At multiple levels, L1/L2 vs. RAM, RAM vs. disk, node vs. network.) So it's still very much tied to changes in hardware.

Whether you call that an "algorithmic improvement" or not is mostly semantics, it would not have been called such in the 80s but it would be today - what properties we consider part of "the algorithm" has also changed to meet hardware changes.

Even whether it's "parallelization" is somewhat semantics - if you change an algorithm to avoid a pipeline stall, is that designing it for parallelization? I guess not because it's single-threaded, but again someone in the 70s/80s might say yes because two things are happening at once.

You're refering to instruction-level parallelism. The parent was refering to thread-level parallelism.

I mean, probably, which is also what I said. But what the parent actually said could also be either.

The point of my comment is that not only are the sorting algorithms changing over time, but what we say constitutes "algorithmic" vs. "implementation" changes also changes over time, so it's really hard to say whether certain changes are "algorithmic" changes or not!

Given that sorting algorithms are evaluated on practical merits on real-world hardware - when the hardware changes, sometimes the sorting algorithm has to change too.

They are just switching from "pure blood" algorithms like merge sort or quicksort, to hybrid and heuristics-based ones. (Not to say these advances are irrelevant though.)

According to the benchmarks, pdqsort only really helps for Go's integer sort.

The fastest way to sort integers is a radix-256 increasing-significance radix sort, and that has been a well-known fact since the 1960's. In other words: a stable bytewise counting sort, sorting from least-significant byte to most-significant byte.

A comparison sort, no matter how clever, will not outperform a radix sort, except for very small arrays or very large (many byte) integers.

Reply on news.ycombinator.com