3 ms·
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 http
by anderskaseorg 7y ago
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 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.
- hinkley 7y agoHow many people do you suppose can read that link?
- kbirkeland 7y agoGoogle scholar returns a pdf[0] when searching the doi. [0] https://epubs.siam.org/doi/pdf/10.1137/0206025 https://epubs.siam.org/doi/pdf/10.1137/0206025
- hinkley 7y agoIt 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.
- cbarrick 7y agoTo 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.
- hinkley 7y agoThis isn’t a tail call situation, though. In order to convert it to iteration you have to use external storage.
- anderskaseorg 7y agoThe 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.