3 ms·
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
by orlp 4y ago
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 https://www.youtube.com/watch?v=2y3IK1l6PI4.
Perhaps the V8 people will be interested in it as well.
- ErikCorry 4y agoCool stuff. Is Glidesort1024 still stable?
- orlp 4y agoYes, it is.
- Traubenfuchs 4y agoThose 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#?
- orlp 4y agoFor 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).
- xeyownt 4y agoWow, this looks very impressive. I thought that sorting algorithms were at a culminating point, but it appears this is not the case at all.
- dgacmu 4y agoI've been interested in this since your presentation in May; any plans to release the source any time soon? (Here's where I hope I'm asking a dumb question and you already have, but I haven't been able to find it.)
- adgjlsfhk1 4y agoHow does the speed compare to a well optimized radix sort?
- orlp 4y agoI haven't compared because they're apples and oranges. The radix sorts do not allow a custom comparison function. I would assume that they're faster, especially if using SIMD.
- adgjlsfhk1 4y agoRadix sorts actually can be used with many custom comparisons by using a sort by api which is enough to let you express many of the uses of custom sorting (e.g. sorting objects by fields, sorting by absolute value, etc). Given the overhead of radix sorts, it wouldn't shock me if this was faster for small sizes.