Hacker News Reader

Comment by kbd | Hacker News Reader

Note that this is true for any (edit: stable, nlogn) merge sort.

Interestingly, the Golang standard library has a sort in it that claims to be a stable in-place O(N log N) mergesort.

Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.

Not 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-d...

Apparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort

you can do merge sort in place

You 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.

Algorithms 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). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array”

Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage.

Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but the semi spaces are still there.

The paper states that each merge operation uses a constant number of pointers. There’s no reason you couldn’t do an iterative merge sort with this in-place merge operation, just like you would with the standard merge operation, to sort with a constant number of pointers.

To be fair, tail calls don't require stack frames.

If it's just a matter of keeping up with the bounds of the partitions, I can see that being done in constant space.

This isn’t a tail call situation, though. In order to convert it to iteration you have to use external storage.

How many people do you suppose can read that link?

Google scholar returns a pdf[0] when searching the doi.

[0] https://epubs.siam.org/doi/pdf/10.1137/0206025

i 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....

I 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.

I 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)

Aha! 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.

Heapsort 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.

A "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.

Thanks for the explanation, interesting.

Stable 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.

Thanks 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.

Said 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.

Reply on news.ycombinator.com