Hacker News Reader

Comment by anderskaseorg | Hacker News Reader

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.

View on HN

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.

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

Reply on news.ycombinator.com