11 ms·
Quadsort: a stable non-recursive merge sort
- aliabd 7y agoMan, that's a good gif
- jerf 7y agoYou may enjoy this: https://www.youtube.com/watch?v=kPRA0W1kECg https://www.youtube.com/watch?v=kPRA0W1kECg There are several similar videos on YouTube demonstrating sorts. If that's a bit sterile for you, you can get a more human touch via the playlist https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7_FK-ySGwHBkltzB11snW7KQ https://www.youtube.com/watch?v=EdIKIf9mHk0&list=PLOmdoKois7...
- aliabd 7y agoThis is terrific
- rthille 7y agoIn the 1990's, NeXT had a demo of their threading capabilities, and you could select a bunch of different sorts to run in parallel. Doesn't seem to be much still "live" on the net about it though: https://www.google.com/search?q=%22SortingInAction%22 https://www.google.com/search?q=%22SortingInAction%22
- loeg 7y agoSeems it's mergesort but with a slightly more complicated comparison primitive.
- proc0 7y agoOr it's like mergesort without the wasted steps that are proportionally less needed as data becomes less random.
- ummonk 7y agoI’ll read the article when I get the chance, but would this be in-place?
- N3XT 7y agoFrom the article: "These operations do require doubling the memory overhead for the swap space." It seems it is not in-place.
- metalliqaz 7y agoI'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.
- davrosthedalek 7y agoYou technically do not need any swap space to swap two numbers. So algorithms which only use swaps could be implemented fully in place.
- utopcell 7y agowhile you can indeed swap in-place for PODs [1], this is not true for c++ objects. Also, in-place swapping is not sufficient for in-place sorting. [1] example: int a, b; a ^= b ^= a ^= b;
- cwzwarich 7y agoThe term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.
- deleted 7y ago[deleted]
- gpderetta 7y agotechnically quick sort needs O(log N) additional space and it is still considered in-place. I guess the threshold for in-place-ness would be less than linear additional space?
- QuinnWilton 7y agoI've never seen a sorting algorithm that uses a non-binary comparison function to order values. Is that a novel technique? It seems really obvious in hindsight, so I'm sure there's just prior art I don't know about.
- tyingq 7y agoPerl and C++ use the <=> "spaceship" operator for that. Cmp for strings in Perl.
- klodolph 7y agoThis is still binary comparison. There are, in general, a number of different sorting algorithms which are optimized for a specific number of elements. In this case, four. It uses five binary comparisons to sort four elements. You can find other algorithms like this, such as an algorithm that uses seven comparisons to sort five items, or one that uses ten comparisons to sort six items.
- QuinnWilton 7y agoAh, I completely misunderstood what was going on with the quad swap at the start. Rereading it makes more sense. Thanks!
- eru 7y agoIf tried that in eg Haskell to see if I can beat the standard library's highly optimized sort. In theory, you can get O(n log k) performance, where k is the number of distinct elements (so k <= n). And crucially: you don't need to know k up-front. In practice, all my attempts were absolutely slower than the standard approach based on binary comparisons only. (But that's saying more about me than about the domain.)
- jph 7y agoSummary: this is a non-recursive merge sort with improvements. Benchmark of quadsort() versus C qsort(): * ~10x faster on forward-order items * ~2x faster on reverse-order items * ~equivalent on random-order items Improvements: * Ordering: when blocks of items are in order, or in reverse-order, then do special case handling, which gives quadsort O(n + log n) instead of qsort O(n * log n). * Boundaries: compare data rather than traditional merge sort wasteful boundary checks.
- eru 7y agoIf you have a k sorted (or reverse sorted) blocks, you can get O(n log k) performance in merge sort variants. Especially, if k is a small fixed constant, like 1 or 2 or 10, you should get linear performance. A few language's standard library sorts implement that already. For a serious implementation, of course, you not only care about the asymptotic performance, but also absolute runtimes.
- chalst 7y agoGood summary. Quibble: O(n + log n) = O(n).
- kannmig 7y agoI think OP made the distinction intentional to “show their working”, so to speak.
- proc0 7y agoInteresting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.
- Hendrikto 7y ago> I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested The search space is infinite, so exhaustively exploring it is impossible.
- foota 7y agoNit: it's possible that there is a finite number of Pareto optimal sorting algorithms, and it may be possible to enumerate those.
- dhash 7y agoOh man if I could efficiently enumerate algorithms across the Pareto front of anything I’d be a happy camper. Procedures that enumerate Turing machines are generally very easy, or nigh impossible
- foota 7y agoYou'd probably want to start by defining equivalence and then work from there. If your criteria for equivalence is loose enough you're already done, e.g., if you just look at runtime big O for randomized arrays or something you can't do better than n lg n so there's just the one Pareto optimal choice, with many possible implementations.
- eru 7y agoIt depends on your model of computation. O(n log n) is only the frontier for comparison based sorts that know nothing about the distribution of inputs. If your sorting algorithm is allowed to do anything else on your data, like hashing or looking at bits or arithmetic, different lower bounds might apply.
- zhangxp1998 7y agoqsort has to invoke your comparison function repeatedly, which incurs a lot of overhead. Try C++'s std::sort
- zhangxp1998 7y agoSee https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0dbf2d862a https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... for a comparison of quadsort with C++'s std::sort. The compare functions are inlined.
- thedance 7y agoThanks for saving us the time. The punch line: Summarize: Slower than std::sort except on random tail. Also a very important tidbit that std::sort is 10x faster than c's qsort for ordered inputs.
- alexchamberlain 7y agoThis feels a little unfair; the function is invoked the same number of times, but C++ has a mechanism for removing the overhead of calling a function (inlining).
- zhangxp1998 7y agoI looked at disassembly of generated binary, sure, function calls inside quad sort were also inlined.
- xucheng 7y agoQuick sort is not the fastest sorting algorithm. It would be nice if there is a benchmark comparing with other state of the art algorithms like Timsort.
- nwellnhof 7y agoIt depends on the implementation but Quicksort typically beats Timsort with random data. Quicksort is unstable though, so that's not a fair comparison.
- nneonneo 7y agoHow does this fare against Python's famous Timsort (used by several languages and systems)? How about the dual-pivot quicksort used by Java for primitive arrays? Someone has to have put together a nice benchmark for comparing many sorting algorithms. I wish that the author had done some benchmarking first, so that the proposed algorithm can properly be positioned w.r.t. state-of-the-art techniques.
- deleted 7y ago[deleted]
- labawi 7y agoAFAICT dual-pivot quicksort is not a stable sort, so quadsort should fare better if actually need a stable sort.
- monadic2 7y agoI’d like to see this too but benchmarking sort algorithms is a pain in the ass due to the wide array of sorting shapes and sizes, I wouldn’t expect a well maintained benchmark suite for language X.
- kccqzy 7y agoThis reminds me of a programming exercise I was asked to write when I first learned programming: write a sorting program generator that given N, generates a program that sorts an array of N elements optimally: the generated code has N! branches, one for each possible permutation. With some CSE help from the compiler, it can be really quite fast at the expense of code size. The author's explanation isn't entirely clear, but it seems similar to the above construction with a fixed N and then a merge sort afterwards.
- gizmo686 7y agoA program generator seems rather advanced for a beginner's assignment... When I started, I wrote an Excel spreadsheet to generate what I would now describe as a 50 element array. I also recall seeing a project to programatically generate mnemonic operators in Haskell, limited only by the ability of the compiler to not run out of memory. Sadly, I can't seem to find it.
- kccqzy 7y ago> A program generator seems rather advanced for a beginner's assignment... Ha, it's nothing more complicated than string concatenation.
- praptak 7y agoA truly optimal sorting for a given N is a nontrivial problem. By truly optimal I mean the actual absolute minimum in the number of comparisons, no O(...) approximation. For five elements the lower bound from counting the permutations is ceil(log2(5!)) which says you cannot sort 5 elements in less than 7 comparisons. An actual 7 comparison algorithm exists but it is not very easy to write it. For greater numbers it gets much much trickier - in general the log(#permutations) lower bound cannot be met.
- kccqzy 7y agoAgreed. My use of the word "optimal" in the original comment was a bit careless.
- xeeeeeeeeeeenu 7y agoIn his benchmark, the author is assuming that qsort() is implemented using quicksort, but that's not necessarily true. For example, glibc is using mergesort (although it falls back to quicksort if the system is short on memory).
- hinkley 7y agoI can’t imagine the sort of bugs you get when your code relies on stable sort but calls qsort and everything works great until the machine is under heavy load.
- Sean1708 7y agoThe most annoying part of development, your users can and will rely on any observable behaviours of your software.
- hinkley 7y agoSomeone recently did something very stupid/clever with an API that I wrote. In the code review I initially complained, but then I couldn’t think of any other way to interpret the design. So I guess that’s a feature now. ‘Course later we found a performance problem, but, you know…
- Naac 7y agoSince we're already using O(N) space, it would be interesting to see how this compares to Radix sort[0], which is O(N) space but O(N) time ( due to just hashing everything ). Like others have said, it would be cool to see quadsort stacked up to other current state-of-the-art sorting algorithms. [0] https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort
- stkdump 7y agoSmall nitpick: radix sort has nothing to do with hashing.
- darawk 7y agoA radix sort is a type of hashing, no? You're bucketing the items based on a reduced form projection of them onto some smaller subspace.
- Sean1708 7y agoNope, if you hash the inputs then you won't be able to order them properly.
- namdnay 7y agoI think it's different in that you don't care what the output of a hash is, as long as it's sufficiently unique or whatever. Whereas here the buckets are are intimately tied to the input. It's more of an arithmetic hack I'd say, as it only works on decimal numbers
- chkas 7y agoThis Quicksort is almost twice as fast https://rextester.com/XHCGA23293 https://rextester.com/XHCGA23293
- pvidler 7y agoOnly in the random case. Already sorted in either direction and it's ~10x slower.
- chkas 7y agoWho wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
- simias 7y agoSorting sorted or mostly-sorted arrays is not uncommon in many use cases.
- chkas 7y ago"Mostly-sorted" is a very vague definition.
- seanhunter 7y agoUsually what people mean by mostly sorted in CS is that there is some small K such that each element in the input is no more than K places from the position it would be in if the input was sorted.
- chkas 7y agoAccording to this definition, the "random tail" test data is not "mostly sorted".
- seanhunter 7y ago
- nightcracker 7y agoC's qsort() is notoriously bad because the comparison function isn't inlined, meaning the majority of time is spent in call overhead. Zhangxp1998 ported quadsort to C++ and compared with std::sort and found it to be slower: https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0dbf2d862a https://gist.github.com/zhangxp1998/0e2fa30656c894017d183e0d... Shameless self promotion, if you want a faster sorting implementation, check out pdqsort (https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort) which is almost twice as fast as libstdc++'s std::sort for randomly shuffled integers, and has all sorts of tricks for input distributions with patterns (like pre-sorted, reverse sorted, single out-of-order element appended, etc).
- vhvjkyhkogvv 7y agoComparing a stable sort to a normal sort is unfair. Compare it with std::stable_sort.
- nightcracker 7y agoThat is a fair point, I missed that quadsort is claimed to be stable.
- vhvjkyhkogvv 7y agoToo late to edit but I read the article again and they compares it favorably to qsort so it makes sense to point out it's worse than std sort.
- zhangxp1998 7y agoI agree is unfair. The point of my benchmark was that the OP's claim "quad sort is faster than quicksort" is false.
- abjKT26nO8 7y agolibstdc++'s std::sort doesn't implement quicksort per se. It implements introsort[1]. I'm curious how a pure C implementation of introsort would fare against std::sort. [1]: <https://en.wikipedia.org/wiki/Introsort> https://en.wikipedia.org/wiki/Introsort>
- thdespou 7y agoI'm a bit sceptical because I don't see any mathematical proof. Only benchmarks which do not prove a lot. It may be faster only by a constant factor on a particular machine but for sufficiently large n it would be as fast as mergesort. 1000000 is peanuts. We need to see convergence for about billions+ of numbers.
- mcherm 7y agoNo one is claiming that this sort algorithm (or any other) is asymptotically faster than O(n log(n)). It can be mathematically proved that no sort algorithm can improve on this. The object with sort algorithms is to find one with good constant-factor performance on typical inputs. Frankly, I am more persuaded by the arguments in favor of an algorithm like "Tim-sort", which doesn't claim to micro-optimize hardware more efficiently (that's basically what "better swapping" is claiming), but instead claims that the algorithm is particularly efficient on some commonly-seen patterns (like "partially-sorted", or "pieces of the list are reverse-sorted"). Of course, any kind of argument about why one sort is better than another are inferior to actual benchmarks.
- amcsi 7y agoI'm quite a noob, and this is a bit off-topic, but if it's mathematically proven that no sorting algorithm can be faster then O(n*log(n)), but we know for sure that checking if an array is sorted is O(n), then doesn't that prove that P ≠ NP?
- C4stor 7y agoNo it doesn't, since O(n*log(n)) is in P too. P = NP doesn't imply that the complexity of finding the solution has the exact same complexity than verifying it, just that both are polynomial.
- deleted 7y ago[deleted]
- davuinci 7y agoTo be precise, we can prove that no sort comparison-based algorithm can do better than O(n log(n)) comparisons. There are some variations though that do better than that, though they are not based on comparisons (i.e counting sort, radix sort).
- WillyNourson 7y agoOh lord it's almost 1k long
- msafadieh 7y agoquad_swap64 and quad_sort64 are only about 350 lines combined.