6 ms·
Note that this is true for any (edit: stable, nlogn) merge sort.
by kbd 7y ago
Note that this is true for any (edit: stable, nlogn) merge sort.
- ThreeFx 7y agoNot true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
- beagle3 7y agoNot even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm. Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-demystified-2/ https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-d...
- saagarjha 7y agoApparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
- CraneWorm 7y agoyou can do merge sort in place
- hinkley 7y agoYou can’t. Merge sort copies data back and forth between two spaces the size of the data set. That’s O(n) extra space. I spent some time four summers ago with merge sort. I had a PoC for an in-place algorithm that survived several rounds of poorly selected sample data. That was quite a disappointment. In looking around I believe I ran across several implementations that required sqrt(n) extra space and one that I think claimed log n but was so complicated I never did figure out why it was supposed to work. At least one of these had higher time complexity, but often enough you need to work with data sets that dominate your memory footprint. Even a second array of pointers might push you over.
- z0r 7y agoi couldn't find a direct reference, but i remembered that sedgewick's c++ algorithms book had an in-place iterative mergesort with no auxiliary space. that probably was a false memory, but it seems that there is such a beast: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.5514&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22....
- hinkley 7y agoI remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.
- z0r 7y agoI just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)
- hinkley 7y agoAha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort. If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants. Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.
- anderskaseorg 7y agoAlgorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 (https://doi.org/10.1137/0206025 https://doi.org/10.1137/0206025). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.
- billforsternz 7y agoHeapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existing response). Edit: Whoops, apparently heapsort is not "stable" (not sure what that means actually), sorry.
- srgpqt 7y agoStable sort means that the order of same elements is preserved. For example, sorting strings by length, strings of the same length would retain the same order between themselves as they had before sorting.
- billforsternz 7y agoThanks for the explanation, makes sense. I was tempted to classify this as "irrelevant to me", but then I remembered an application I had recently where I had values (chess games) that I was sorting which I didn't want to reorder if they were adjacent (as far as the sort was concerned) but not identical. Ended up adding an "original order" field as a sort tiebreaker. As it happens a stable sort would have saved me the pain.
- cdirkx 7y agoA "stable" sorting algorithm preserves the relative order of elements with "equal value". This doesn't really apply if you are only sorting simple values, as there is no difference between a 7 and another 7, but does if you are sorted more complicated objects by some key. Example: sorting 2#a, 1#c, 2#b by only the first number. An algorithm that produces 1#c, 2#b, 2#a is a correct sorting algorithm, but not stable as it changes the order of 2#a and 2#b.
- billforsternz 7y agoThanks for the explanation, interesting.
- hinkley 7y agoSaid another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths. One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.
- kragen 7y agoInterestingly, the Golang standard library has a sort in it that claims to be a stable in-place O(N log N) mergesort.