3 ms·

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

rav 5y ago
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.
- deleted 5y ago
  [deleted]
Cthulhu_ 5y ago
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.
- karelpeeters 5y ago
  That's not particularly relevant, no standard library sort method is using multithreading in the background. It actually is about algorithmic improvements.
  - morelisp 5y ago
    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.
    - afr0ck 5y ago
      You're refering to instruction-level parallelism. The parent was refering to thread-level parallelism.
      - morelisp 5y ago
        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!
kreetx 5y ago
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.)
37ef_ced3 5y ago
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.

rav 5y ago

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.

deleted 5y ago
[deleted]

Cthulhu_ 5y ago

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.

karelpeeters 5y ago
That's not particularly relevant, no standard library sort method is using multithreading in the background. It actually is about algorithmic improvements.
- morelisp 5y ago
  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.
  - afr0ck 5y ago
    You're refering to instruction-level parallelism. The parent was refering to thread-level parallelism.
    - morelisp 5y ago
      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!

kreetx 5y ago

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.)

37ef_ced3 5y ago

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.