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

41–50 of 84 posts

Re: Sorting algorithms that don’t hate you

#41

Post by Laakeri »

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…

It's enough to just take one random element and use it as a pivot.

Re: Sorting algorithms that don’t hate you

#42

Post by graycat »

Let n be a non-negative integer.

A number n is bit reversed if it is written was written in binary (base 2) and then the bits were written in reverse order.

Last time I looked at Shell sort, when sorting n records on keys in bit reversed order, the iterations of Shell sort did nothing until the last iteration at which time Shell sort was just bubble sort or some such and, whatever, ran in time O(n^2) where the O() is some obscure but now common notation. The article claims something smaller than O(n^2). Okay, but to get something smaller, have to tweak what used to be a standard version of Shell sort.

For another point, the article wants a stable sort -- if two records (the data being sorted) A and B have equal keys and before the sort record A is before record B, then after the sort record A will still be before record B. But, if want a stable sort, then for one approach, before the sort, number the records and use these numbers as part of the keys. Right this extra step runs in time O(n) and uses extra temporary, working storage proportional to n. For current computing, is this extra storage a meaningful issue?

Re: Sorting algorithms that don’t hate you

#43

Post by ErikCorry »

orlp wrote: post #38

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…

Cool stuff.

Is Glidesort1024 still stable?

Re: Sorting algorithms that don’t hate you

#44

Post by Traubenfuchs »

orlp wrote: post #38

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…

Those numbers look impressive. For stuff like this, can it be said that it should just be implemented as is in the std libs of mainstream languages like Java, Python, C#?

Re: Sorting algorithms that don’t hate you

#45

Post by sakras »

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.

Locality is good during merge but there’s no parallelism - there’s a data dependency between the previous and next iteration because we don’t know which pointer we’re supposed to advance. I think it’s still unclear whether this necessarily is compensated for by the cache locality

Re: Sorting algorithms that don’t hate you

#46

Post by somat »

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.

At one point I used to work at a place that had a production process that used several hundred ibm 3480(if I remember correctly) tape cartridges. I would do a LSB radix sort afterwards to get them back in order.

I think back on it with a certain amount of nostalgia now, but it was a stupid way to do operations, even at the time, They had invested big in computers in the 70's and were still maintaining the same tech stack in the early 00's when I worked there.

Re: Sorting algorithms that don’t hate you

#47

Post by xeyownt »

orlp wrote: post #38

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…

Wow, this looks very impressive.

I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.

Re: Sorting algorithms that don’t hate you

#48

Post by orlp »

ErikCorry wrote: post #43
orlp wrote: post #38

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…

Cool stuff. Is Glidesort1024 still stable?

Yes, it is.

Re: Sorting algorithms that don’t hate you

#49

Post by olliej »

ErikCorry wrote: post #27
olliej wrote: post #6

I am curious about exactly what v8 was doing at the time, because "just use Quicksort" doesn't work for inconsistent comparison functions or mutating data. These issues aren't magically resolved with "use a stable sort", but it means you're not just calling qsort(...) to perform the sort. I vaguely recall JSC actually having a literal tree sort at one point to deal with this.

If you provided an inconsistent comparison function I don't see how it's the sort implementation's responsibility to produce a sensible output. Or even to terminate at all.

What are you talking about?

This is in a JS engine, where by design all code is untrusted.

If you are a JS engine, then arbitrary code execution, failure to terminate, or crashing is never an acceptable outcome, regardless of how bad the code is, because again, you're dealing with untrusted input. The assumption for a JS engine is necessarily that all code is malicious.

Re: Sorting algorithms that don’t hate you

#50

Post by orlp »

Traubenfuchs wrote: post #44
orlp wrote: post #38

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…

Those numbers look impressive. For stuff like this, can it be said that it should just be implemented as is in the std libs of mainstream languages like Java, Python, C#?

For C#, it is very similar to Rust, so I would say yes. I'm too unfamiliar with the JVM and its performance characteristics to say for sure for Java, but probably also yes. However, the performance characteristics of Python are so different to Rust that I think it's safe to say a different approach will likely end up better (one that focuses on minimizing indirections and comparison function invocations).
Post reply on HN