Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting algorithms that don’t hate you

medium.com

Post reply on HN
Print view View original

31–40 of 84 posts

Re: Sorting algorithms that don’t hate you

#31

Post by makeset »

dataflow wrote: post #16
bee_rider wrote: post #14

Earlier quoted context omitted.

In the rare event that you have to sort a big stack of paper, merge sort is also super intuitive and easy to apply by hand.

I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.

Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.

Re: Sorting algorithms that don’t hate you

#32

Post by bee_rider »

makeset wrote: post #31
dataflow wrote: post #16

Earlier quoted context omitted.

I like to think so but I'm not sure that's true. At least I don't think I've ever seen anyone divide a stack in half, then divide the left one in half, then divide the left one of that in half, etc. as if they're doing recursive mergesort. I feel like most people start from the first card and build upward, either with insertion sort or with something like iterative mergesort.

Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.

Hey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.

Re: Sorting algorithms that don’t hate you

#33

Post by noitpmeder »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker. (With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the differen…

Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.

And if they're not completely equal?

Re: Sorting algorithms that don’t hate you

#34

Post by ErikCorry »

halayli wrote: post #10
marginalia_nu wrote: post #3

An understated benefit of merge sort is that all of its access patterns have excellent locality. Regardless of big-O, this is a huge advantage because it reduces cache thrashing. Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.

Quite the opposite. Merge sort is much more susceptible to cpu cache misses. You have to go out of your way to optimize mere sort to avoid cache issues. But the devil is in the details and it really depends on the arch, the dataset you're sorting (numbers vs strings makes a big difference), cores and cache levels available, memory available.

In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median.

Collecting those nine elements looks terrible for locality.

Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implementing it.

Re: Sorting algorithms that don’t hate you

#35

Post by tgv »

hypertele-Xii wrote: post #13
chrchang523 wrote: post #8

Note that it is straightforward to modify an unstable sort algorithm into a stable one, when it’s okay to use O(n) extra memory: define an array that tracks each element’s original position, and when two elements otherwise compare equal, use the original position as the final tiebreaker. (With that said, Timsort must be faster in practice than this kind of retrofitted unstable sort. I’m curious how large the differen…

Isn't that completely unnecessary? Do a deeper comparison. If the elements are absolutely equal, then it doesn't matter.

I'll spell it out then: you don't always need to sort based on the entire object's value. Comparing the whole object can be pretty expensive when you only need to sort by one field.

Re: Sorting algorithms that don’t hate you

#36

Post by gpderetta »

ErikCorry wrote: post #34
halayli wrote: post #10

Earlier quoted context omitted.

Quite the opposite. Merge sort is much more susceptible to cpu cache misses. You have to go out of your way to optimize mere sort to avoid cache issues. But the devil is in the details and it really depends on the arch, the dataset you're sorting (numbers vs strings makes a big difference), cores and cache levels available, memory available.

In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median. Collecting those nine elements looks terrible for locality. Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implement…

To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.

Re: Sorting algorithms that don’t hate you

#37

Post by ErikCorry »

gpderetta wrote: post #36
ErikCorry wrote: post #34

Earlier quoted context omitted.

In practice, to avoid worse case quadratic time, you have to have a rather involved pivot selection in Quicksort. Eg nine random or evenly distributed elements which you put in three groups of three and take the median of the median. Collecting those nine elements looks terrible for locality. Funnelsort is a cache oblivious variant of merge sort which is provably cache optimal in some sense. I haven't tried implement…

To handle quadratic edge cases you would switch to heapsort when the recursion depth goes above the threshold. I.e. introsort; no need for convoluted pivot selection methods.

That's usually called Introsort, but I think you'll find that most of these still consider at least the middle element for a pivot, so they still have a more complex cache behaviour than the naïve linear sweep from both ends of a simple Quicksort.

https://en.wikipedia.org/wiki/Introsort#Implementations

And heapsort has terrible cache behaviour.

Re: Sorting algorithms that don’t hate you

#38

Post by orlp »

At FOSDEM 2023 I will be presenting glidesort in the Rust room.

It is a new stable sorting algorithm that is a hybrid of quicksort and mergesort which is much faster for random data, while still taking full advantage of pre-existing order or inputs with many duplicates. On an Apple M1 in Rust the latest version is ~4.5x faster than the stdlib slice::sort for sorting 2^25 random integers while using 4 times less extra memory. It is 11.5x faster if you happen to sort only 4096 distinct integers with many duplicates. Note that the algorithm is purely comparison based and does not contain special type-dependent SIMD stuff.

I have a short preliminary talk on glidesort here: https://www.youtube.com/watch?v=2y3IK1l6PI4.

Perhaps the V8 people will be interested in it as well.

Re: Sorting algorithms that don’t hate you

#39

Post by HelloNurse »

bee_rider wrote: post #14
marginalia_nu wrote: post #3

An understated benefit of merge sort is that all of its access patterns have excellent locality. Regardless of big-O, this is a huge advantage because it reduces cache thrashing. Like it probably doesn't matter if you're sorting 10k entries, but when you're sorting several gigabytes it really does.

In the rare event that you have to sort a big stack of paper, merge sort is also super intuitive and easy to apply by hand.

Merging stacks of papers by hand isn't the same as exchange-based computer mergesort: if the cost of inspecting and comparing items is negligible relative to actually moving them the basic, unit cost operation is splitting a sequence into three possibly empty sequences and splicing the middle piece into an arbitrary position in another sequence. In some cases reversing the spliced sequence is free ("pancake" sorting).

This cost model is an important reason to merge bottom up, from sorted subsequences, without arbitrary splitting that can add work but not reduce it.

Re: Sorting algorithms that don’t hate you

#40

Post by adwn »

bee_rider wrote: post #32
makeset wrote: post #31

Earlier quoted context omitted.

Because without the insertion cost of fixed locations, insertion sort is also NlogN: just a binary search per element.

Hey wait, good point, what the heck kind of data structure even is a stack of papers? You can insert like a linked list but hop around like an array.

Only for reasonably small stacks. Insertions at random indices won't stay O(1) when you're dealing with 100k pages and more – i.e., when you can't pick them up in one movement.
Post reply on HN