7 ms·
WikiSort – Fast, stable, O(1) space merge sort algorithm
- jsonified 13y agonice to see even in sort() we have innovation!
- chrismonsanto 13y agoIf you're interested in alternative sort algorithms, you might enjoy the self-improving sort [1]. A simplified tl;dr: given inputs drawn from a particular distribution + a training phase, the result is a sort that is optimal for that particular distribution. The complexity is in terms of the entropy of the distribution, and can beat the typical worst case O(n log n) for comparison sorts. [1]: http://www.cs.princeton.edu/~chazelle/pubs/selfimprove.pdf http://www.cs.princeton.edu/~chazelle/pubs/selfimprove.pdf
- apples2apples 13y agoHow does it compare to an O(1) space version of quicksort?
- astrada 13y agoquicksort is not a stable sort (http://en.wikipedia.org/wiki/Stable_sort#Stability http://en.wikipedia.org/wiki/Stable_sort#Stability)
- beagle3 13y agoQuicksort is worst case O(n^2) time, unless you incorporate something like Quickselect for your pivot (which no one ever does, because it makes it relatively complicated. Have you ever seen an O(n log n) guaranteed quicksort implemented? I haven't - best I've seen is median-of-3 or median-of-5 pivots - or randomized). Furthermore, I've never seen an O(1) space version of quicksort and I'm not sure one can exist -- see, e.g. http://stackoverflow.com/questions/11455242/is-it-possible-to-implement-quicksort-with-o1-space-complexity http://stackoverflow.com/questions/11455242/is-it-possible-t... The meaningful comparison would actually be to Heapsort, which is in-place, O(1) space, and NOT stable - though much, much, simpler. ADDED: Anyone who uses quicksort should read this gem from Doug McIlroy, which elicits an O(n^2) behaviour from most quicksort implementations: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf -
- klmr 13y agoMany/most widely used “quicksort” implementations are actually introsort (in particular, `std::sort` is), and thus O(nlogn) worst case.
- anonymoushn 13y agoThere is no O(1) space version of quicksort.
- sesqu 13y agoI've been meaning to compare various in-place mergesorts, so this'll definitely make it into my bookmarks.
- taylorbuley 13y agoI'm sure people will loathe me for saying this, but I'd really like to see the implemented into JavaScript. We've got Crossfilter (https://github.com/square/crossfilter/wiki/API-Reference); https://github.com/square/crossfilter/wiki/API-Reference); however, as more data moves client-side with storage APIs like IndexedDB, I see a need for "as efficient as possible"
- hltbra 13y agoCrossfilter's link is broken (parenthesis and semicolon were included).
- phillmv 13y ago1. Skimming the paper, it only matters if you need an efficient stable sort. If you just need O(1) memory you can stay with heapsort, which at least will have more reference implementations. This lead me to look up browser sort implementations; http://stackoverflow.com/questions/234683/javascript-array-sort-implementation http://stackoverflow.com/questions/234683/javascript-array-s... - it seems Moz uses mergesort and Webkit may or may not do something silly for non contiguous arrays. So, there could be a use for it. For most applications you're about fine as it is. 2. I'm interested in hearing about applications where you're loading millions of array elements in people's browsers. I was going to be cranky and make rude comments but I can envision people wanting to play with their data without loading it in specialized toolsets/learn R/build a DSL in $lang_of_choice.
- iandanforth 13y agoI do some ML in browser for ease of visualization/portability. Don't often need to sort all the connection weights, but hey you asked :)
- taylorbuley 13y agoHere's my work-in-progress visualization with a dataset of 1 million+ IMDB entries to be stored in IDB http://dashdb.com/#/ http://dashdb.com/#/ It purposefully pushes IDB way further than it should be taken in most cases.
- dignati 13y agoThis has a really nice documentation, should make it easy to implement.
- danbruc 13y agoDespite the good documentation this algorithm is complex and I bet most implementations will be incorrect. UPDATE: I could not find the article I had initially in mind but I found this one [1] showing that even prominent implementations of simple algorithms like binary search or quicksort contain bugs more often than one expects and they may even remain unnoticed for decades. So take this as a warning - if you implement this algorithm you will almost surely fail no matter how smart you are or how many people look at your implementation. [1] http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.de/2006/06/extra-extra-read-a...
- datawander 13y agoThere is also a complete lack of tests. It'd be nice if there was a library of tests for all sorting algorithms. I'm sure there is, but something more widely accepted and well known.
- beagle3 13y agoPrevious innovation that I remember in sorting was Python's TimSort - it's just MergeSort with a few tweaks, but it's better than any other sort I've met when applied to real world data.
- masklinn 13y ago> it's just MergeSort with a few tweaks "a few tweaks" is a bit of an understatement, at a high-level it's a hybrid of insertion and merge sort (it's an insertion sort below 64 elements, and it uses insertion sorts to create sorted sub-sections of 32~64 elements before applying the main merge sort)
- beagle3 13y agoYes, it is a bit of understatement. Other than the insertion at smaller sizes, it adds: - scans array to find merge-able runs (rather than use a "standard" size like more merge sorts); This makes it closer to O(n) for mostly-sorted arrays, a feature that is mostly associated with Bubble Sorts - but without giving up any of the good things about MergeSort - identifies "reverse runs", and just reverses them - making mostly-reverse-sorted arrays closer to O(n), which no other general sort achieves. It's still O(n log n) in the worst case - but it just works exceptionally well on real life datasets, which often have sorted or reversed sections.
- TwoBit 13y agoOur benchmarks consistently show Tim sort as the fastest -stable- sort, But intro sort consistently beats it.
- beagle3 13y agoWhich benchmarks would that be? TimSort as implemented in Python goes through the Python machinery of object comparison and object management in general. Make sure you do an apples<->apples comparison when benchmarking.
- TheLoneWolfling 13y agoIs there a way that better minds than me can see to parallelize this algorithm?
- deleted 13y ago[deleted]
- stokedmartin 13y agoThe merge step[0] can be parallelized - - take the two sorted arrays A & B (assume both are of size n) and make partitions of size log n in one of them, let's say A - Now considering there are n/logn processors, assign each partition to a processor. On each partition take the last element (l) and do a binary search to find a cut point in the other array B such that all elements in B are <= l. Cut points of two such partitions in A correspond to a partition in B which can then be sequentially merged by the processor. Span is O(log n); Work is O(n); so parallelism is O(n/logn) Detailed information here [1] [0] https://github.com/BonzaiThePenguin/WikiSort/blob/master/Chapter%203:%20In-Place.md https://github.com/BonzaiThePenguin/WikiSort/blob/master/Cha... [1] http://electures.informatik.uni-freiburg.de/portal/download/3/6950/ http://electures.informatik.uni-freiburg.de/portal/download/...
- bmvakili 13y agoI got widely different results there: C - 105.868545% C++ - 80.0518% Java - 61.664313124608775% Probably the optimizations there; can't easily be done in Java one; interesting nonetheless, thanks for post.
- michaelmior 13y agoWhat are your result numbers supposed to mean?
- pjscott 13y agoThose benchmark ratios are not comparable across languages. The C code compares running time with a very standard mergesort. The C++ code compares with std::stable_sort. The Java code compares with a standard mergesort -- very similar to the code in the C version -- but has hard-to-predict JIT warmup effects.
- jokoon 13y agowhy is a sort function so important ? I mean what sorts of big data sets are you sorting that much often ?
- rguldener 13y agoBelieve it or not, sorting is one of the most common operations software performs. As a simple example think of how many times somebody queries something like `SELECT (...) FROM huge_table WHERE (...) ORDER BY (...)` Obviously the order by means the data needs to be (at least partially) sorted before it can be returned. To be fair that is a different case algorithmically since DB's are almost never able sort entirely in memory. But there are plenty of other examples where in memory sorting is necessary or provides advantages for later computation steps (eg. ability to cut of elements larger than a certain threshold).
- jokoon 13y agoyeah but it's already implemented into db software, why would devs reinvent the wheel ?
- thaumasiotes 13y agoBecause "do it once, never improve again" is a bizarre philosophy?
- jokoon 13y agoI think most db software are already quite well optimized. I mean unless you're a db software dev, and unless you're profiling it for each use case I wonder if you can really find something to optimize. I just meant that's it's a niche. I honestly got no idea how db software are programmed but I doubt any dev can pretend to do better. I guess that algorithm would interest people who recompile their db software, or who don't use those db software. So here comes the question : what are the pro cons of using a db software ? Why would some devs still use plain files to store data ?
- 13y ago
- beagle3 13y agoAlso, interesting discussion on reddit: http://www.reddit.com/r/programming/comments/20fxv8/making_a_fast_and_stable_sorting_algorithm_with/ http://www.reddit.com/r/programming/comments/20fxv8/making_a...
- _delirium 13y agoTo be pedantic, in-place sorting algorithms (typically?) take O(log n) space, not O(1). They don't copy the data to be sorted, but they do need some temporary space that isn't fixed, but scales (slowly) with the size of the array being sorted. The usual sources of the log-n space growth come from either a stack recursing on things (explicitly or implicitly) and/or the array indices. This particular implementation (looking at the C version) uses fixed-size 'long ints' for its temporary data storage, which means it only works on arrays up to LONG_MAX elements. If you had larger arrays, your need for temporary data would grow, e.g. you could upgrade all those long ints to long long ints and accommodate arrays up to LLONG_MAX. Of course, logarithmic growth is very slow.
- detrino 13y agoHeap sort is an example of an in-place sorting algorithm that is constant space. Just because this implementation uses some kind of fixed size buffer, doesn't mean it has an upper limit for the amount of data it can sort. It is possible, but probably requires a deeper understanding of the algorithm to know for sure.
- _delirium 13y agoMaybe I'm missing some way of implementing heapsort without array indices, but all the implementations I've seen use O(log n) space. For example, the pseudocode on Wikipedia (https://en.wikipedia.org/wiki/Heapsort#Pseudocode https://en.wikipedia.org/wiki/Heapsort#Pseudocode) at a quick glance uses five temporary variables: 'count', 'end', 'start', 'child', and 'root'. How much temporary space is this? Well, proportional to the log of the size of the array, at a minimum. If you're sorting 256-element arrays, these can each be 8-bit integers, and you need 5 bytes of temporary space. If you're sorting a 2^32 element array, these need to each be at least 32-bit integers, and you need 20 bytes of temporary space. If you have a 2^64 element array, they need to be 64-bit integers, and you need 40 bytes of temporary space. If you have a 2^128 element array, they need to be 128-bit integers, and you need 80 bytes of temporary space. Therefore, temporary space needed grows with the log of the array size. Which is very slow growth, but still growth! The two things you can do are: 1) pick a fixed-size int and cap the max size of array you can handle; or 2) use a bigint datatype, and the size of your bigints will (asymptotically) grow with log(n).
- zenciadam 13y agoIt's the quarterly post from the guy who just reinvented radix sort.
- tbingmann 13y agoI made a video of how the algorithm works: http://youtu.be/NjcSyD7p660 http://youtu.be/NjcSyD7p660 To make it I needed a C++ version with iterators, which I though would be faster. But it is still about 20% slower than stable_sort for the default random input test. It probably also stays the same for other inputs.