Hacker News Reader

Comment by hinkley | Hacker News Reader

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.

View on HN

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.

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

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.

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.

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.

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.

Reply on news.ycombinator.com