7 ms·

Faster than radix sort?

by throwaway12245 4y ago

EGreg 4y ago
Faster than quicksort?
- hajile 4y ago
  Beating quicksort alone is almost always as easy as swapping insertion sort once you get down to around 14 elements. This is used by C#'s quicksort (which also swaps to heapsort after a depth of 32 IIRC) and also in Timsort in JS, Java, Python, etc.
- repiret 4y ago
  Quicksort isn’t stable.
  - orlp 4y ago
    Schoolbook exchange quicksort isn't stable, but quicksort absolutely can be implemented stably, which I do in glidesort: https://www.youtube.com/watch?v=2y3IK1l6PI4 https://www.youtube.com/watch?v=2y3IK1l6PI4.
    - janwas 4y ago
      Further to that, many use cases of Quicksort have unique keys, so stable is the same as unstable. Example: ascending indices appended to the key, when sorting large records where we don't want to move around the entire record.
- scandum 4y ago
  Blitsort is a hybrid quicksort, see title. It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort https://github.com/scandum/crumsort
smingo 4y ago
Not for big arrays. Radix sort is O[n] . (or [n * number of bytes in Int] or whatever is being compared). It's omitted from the comparisons, I see. Radix sort can also have predictable memory overhead.
- bugfix-66 4y ago
  Radix sort is also very simple, e.g., https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054... And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/ https://sorting.cr.yp.to/
- naasking 4y ago
  Radix sort is theoretically O(N), but memory access is logarithmic so in reality you can't do better than O(log N) no matter what algorithm you use. Only constant factors matter at that point. Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench
  - ben-schaaf 4y ago
    random memory access has a non-constant upper bound (assuming infinitely ever larger and slower caches), but radix sort is mostly linear memory access.
  - hinkley 4y ago
    Also radix is a pretty special case because it assumes you want to sort by some relatively uninteresting criteria (be honest, how often are you sorting things by a number and only a number?). What happens in the real world is that the size of fields you want to sort on tends to grow in log n. If you had half a billion John Smiths using your service you’d use some other identifier that is unique, and unique values grow in length faster than logn. I’m glad other people are having this conversation now and not just me.
    - henrydark 4y ago

Faster than radix sort?

EGreg 4y ago

Faster than quicksort?

hajile 4y ago
Beating quicksort alone is almost always as easy as swapping insertion sort once you get down to around 14 elements. This is used by C#'s quicksort (which also swaps to heapsort after a depth of 32 IIRC) and also in Timsort in JS, Java, Python, etc.
repiret 4y ago
Quicksort isn’t stable.
- orlp 4y ago
  Schoolbook exchange quicksort isn't stable, but quicksort absolutely can be implemented stably, which I do in glidesort: https://www.youtube.com/watch?v=2y3IK1l6PI4 https://www.youtube.com/watch?v=2y3IK1l6PI4.
  - janwas 4y ago
    Further to that, many use cases of Quicksort have unique keys, so stable is the same as unstable. Example: ascending indices appended to the key, when sorting large records where we don't want to move around the entire record.
scandum 4y ago
Blitsort is a hybrid quicksort, see title. It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort https://github.com/scandum/crumsort

smingo 4y ago

Not for big arrays. Radix sort is O[n] . (or [n * number of bytes in Int] or whatever is being compared). It's omitted from the comparisons, I see. Radix sort can also have predictable memory overhead.

bugfix-66 4y ago
Radix sort is also very simple, e.g., https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054... And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/ https://sorting.cr.yp.to/
naasking 4y ago
Radix sort is theoretically O(N), but memory access is logarithmic so in reality you can't do better than O(log N) no matter what algorithm you use. Only constant factors matter at that point. Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench
- ben-schaaf 4y ago
  random memory access has a non-constant upper bound (assuming infinitely ever larger and slower caches), but radix sort is mostly linear memory access.
- hinkley 4y ago
  Also radix is a pretty special case because it assumes you want to sort by some relatively uninteresting criteria (be honest, how often are you sorting things by a number and only a number?). What happens in the real world is that the size of fields you want to sort on tends to grow in log n. If you had half a billion John Smiths using your service you’d use some other identifier that is unique, and unique values grow in length faster than logn. I’m glad other people are having this conversation now and not just me.
  - henrydark 4y ago