11 ms·
Blitsort: A fast, in-place stable hybrid merge/quick sort
- throwaway12245 4y agoFaster than radix sort?
- EGreg 4y agoFaster than quicksort?
- hajile 4y agoBeating 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 agoQuicksort isn’t stable.
- orlp 4y agoSchoolbook 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 agoFurther 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 agoBlitsort 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 agoNot 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 agoRadix 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 agoRadix 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 agorandom 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 agoAlso 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
- dleslie 4y agoWoah, I like the solid memory guarantees. Could be useful for embedded projects.
- mmoskal 4y agoSeems to use quite a bit of stack for an embedded usage. An interesting thing to note: microcontrollers are typically memory-bound when using common algorithms - while they are maybe 100x slower than a desktop computer they have say 1000000x less RAM. So, for example, a GC cycle would be often in the range of 1ms.
- odo1242 4y agoWouldn’t a GC cycle be short if the microcontroller had less RAM? (as a genuine question)
- mmoskal 4y agoWell yes. The less heap to scan the faster it is. I was just referreing to the unusual ratio between speed and RAM.
- naasking 4y ago1ms is pretty short. GC cycles on desktops and servers can take hundreds of ms.
- adgjlsfhk1 4y agoI've seen pathological examples where a gc takes 30 seconds
- logicallee 4y agoGC is the bubblesort of our era. I mean it seems to be a very inefficient way to solve a problem. I hope computer scientists will come up with something better than GC.
- that 4y agoHeads up: No license given in the repo, be careful if you are thinking of using this for a project. EDIT: Retracted -- did a search like for "license", but apparently the search results omits variants like "sublicense" which would have caught the MIT license at the beginning of the source file: https://github.com/scandum/blitsort/search?q=license https://github.com/scandum/blitsort/search?q=license vs. https://github.com/scandum/blitsort/search?q=sublicense https://github.com/scandum/blitsort/search?q=sublicense
- HillRat 4y agoStandard MIT licensing's attached to the source code itself.
- sergiotapia 4y agohttps://github.com/scandum/blitsort/blob/main/src/blitsort.c#L1 https://github.com/scandum/blitsort/blob/main/src/blitsort.c...
- that 4y agoAh "sublicense" seems to be the keyword to find there otherwise a search comes up empty: https://github.com/scandum/blitsort/search?q=license https://github.com/scandum/blitsort/search?q=license
- deleted 4y ago[deleted]
- blondin 4y agothanks for sharing this with us. i admire this approach that builds on small improvements here and there. and these improvements are interesting in their own way. it reminds me of micro-optimizations with encoding routines. i didn't SIMD in the code at first glance. you might gain significant speed with SIMD.
- janwas 4y ago:) Indeed, we're seeing 10x speedups from SIMD for some distributions. It's useful both for sorting networks and quicksort partitioning. Code here: https://github.com/google/highway/tree/master/hwy/contrib/sort https://github.com/google/highway/tree/master/hwy/contrib/so... (disclosure: I'm one of the co-authors).
- g0xA52A2A 4y agoOn mobile at the moment but it will be interesting to see how this compares to Glidesort [1]. Though I don’t think it’s been released yet. [1] https://m.youtube.com/watch?v=2y3IK1l6PI4 https://m.youtube.com/watch?v=2y3IK1l6PI4
- orlp 4y agoHello, author of glidesort (and for context, pdqsort) here. No it's not released yet but it's getting real close. The code is virtually done, with some minor cleanup required. Besides some personal stuff, a large source of my delay has been the headache that is panic safety in Rust. Non-trivial sorting code becomes extra difficult if a forced stack unwinding can occur every time you compare two elements, where you are then required to fully restore the input array to a valid state. Doubly so if you can't even assume the comparison operator is valid and obeys the strict order semantics. I am currently in the process of writing a paper I want to publish along glidesort which is also mostly done. Since the linked talk I've also had some more performance wins making it ~4.5 times faster than std::stable_sort for uniform random integers and much more than that for low cardinality data and input patterns. Glidesort can use arbitrary amounts of auxiliary memory if necessary, but is fastest when given a fraction of the original input array worth of memory - I'm currently planning on releasing it with n / 8 as the default. I haven't looked at blitsort in detail but I am skeptical of the O(n log n) claim, I believe it is O(n (log n)^2) like glidesort is when given a constant amount of memory, as blitsort's partition and merge functions are recursive. Not that this really matters in practice - ultimately the real runtime is what matters. But I wouldn't be surprised to see blitsort slow down more relative to the competition for larger inputs.
- scandum 4y agoIt should be O(n log n) comparisons and technically O(n (log n)^2) moves. The moves are reduced by a relatively large constant however, and blitsort might qualify as O(n log n) moves when given sqrt(n) aux. In your Youtube presentation you do seem to skip mentioning that many of the performance innovations in glidesort were derived from quadsort and fluxsort. Some credit in your upcoming paper would be much appreciated. Feel free to email me if you have any questions, some things like my first publication of a "branchless" binary search in Aug 2014 may be hard to find, though there might be prior claim. ~4.5 times faster than std::stable_sort for uniform random integers is pretty impressive. Is this primarily from increasing the memory regions from 2 to 4 for parity merges / partitions? I'm benching on somewhat dated hardware and had mixed results (including slowdowns), so I never went further down that rabbit hole.
- JaneLovesDotNet 4y agoDumb questions from a programmer who is weak at math. 1) Is there a theoretical minimum assymptotic speed for sorting? 2) Some of these newer sorts seem to have arbitrary parameters in them (e.g. do X if size of set is smaller than Y). Are we likely to see more and more complex rule sets like that lead to increased sorting speeds?
- m12k 4y ago1) IIRC the best case is O(n) (you just verify that it is already sorted, can't get much faster than that) while the worst case is O(nlog(n)). But some of the best algorithms in real world usage have worse worst case asymptotic speed. 2) I think things like cache and machine word size have huge impact on real world speed, so it makes sense to have knobs to tweak to fit within those limits, even enough a theoretical analysis does away with constants like that
- user5678 4y ago
- brap 4y ago> the worst case is O(nlog(n)) I think it's worth clarifying that this is the best worst case possible, i.e for every sorting algorithm you could create a certain input in a way that it won't be able to beat O(nlog(n)). In other words, O(nlog(n)) is a minimum hard limit for worst case speed, no algorithm can do better than O(nlog(n)) on all possible inputs (but it can do better on some inputs, o(n) being the hard limit there). I don't really remember the theory behind this, but hopefully someone here can answer: is it theoretically possible for a sorting algorithm to achieve sub-O(nlog(n)) speeds on 99.99% (or some other %) of randomly selected inputs? Or even O(n)?
- kjeetgill 4y agoPeople forget! The O(nlogn) limit for the best worst case is for comparison sorts. I don't know if you consider it a "special case", but for more cases than not you can do guaranteed linear time to the number of elements: Radix and Bucket Sort. This is O(n) for things like ints because the number of bits are constant but for strings the length plays a factor: O(k*n). This performance isn't dependent on the distribution of items being sorted so I'd consider that pretty general. You could also consider things like sleep sort or spaghetti sort: googling them I'll leave to the reader. Oh, and sorting networks are a good read too.
- ZhongDongLong 4y agoIs there a TrollSort? I'm thinking of an algorithm which initially seems to be fast and efficient but takes exponentially longer time with larger arrays and exponentially longer towards the end of sorting.
- justansite 4y agoNot sure if this qualifies, but the first thing that came to mind for me was bogosort sometimes called bozosort. https://en.m.wikipedia.org/wiki/Bogosort https://en.m.wikipedia.org/wiki/Bogosort
- jansan 4y agoSince the sorting scene seems to be fully assembled in this thread, I take the opportunity to ask quick question about a use case that does not seem uncommon: Is there an algorithm that is especially efficient if the array contains many sorted sequences, and still works alright for fully shuffled arrays? And are there algorithms that should be avoided in these cases.
- scandum 4y agoQuadsort, fluxsort, blitsort, and crumsort all qualify depending on your needs. skasort_cpy is pretty good on 32 bit integers if you give it n auxiliary memory. rhsort is very good and likely the best for 31 bit integers, but a bit rough around the edges still, and doesn't work well on arrays above 1M elements. Avoid radix sorts for 64 bit integers, they're ideal for 16 bit. glidesort is promising, though I haven't seen it benched against the latest fluxsort / blitsort. Timsort's main problem is that it's slow on shuffled arrays. pdqsort and other introsorts aren't good on semi-ordered data.
- k2xl 4y agoQuestion: are any of these novel sorting algorithms being used in modern databases or tech stacks?
- ismailmaj 4y agopdqsort by Orson Peters is used in Rust std for `sort_unstable`. https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort_unstable https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...