Virtual-Memory Powersort
For practitioners needing stable sorting with limited memory, this provides a practical algorithm that is nearly as fast as standard mergesort but uses far less space.
Virtual-Memory Powersort reduces the memory consumption of adaptive mergesort from O(n) to O(√(n log n)) while maintaining the same number of moves and comparisons up to an additive O(n) term, achieving almost in-place stable sorting with negligible overhead in many scenarios.
We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption of the algorithm; specifically, for sorting $n$ objects the required buffer area is reduced from space for $n/2$ objects to $O(\sqrt{n \log n})$ objects. While this space-efficiency can be achieved (indeed reduced to $O(1)$) conceptually very easily with known inplace merging algorithms, using these as a drop-in replacement for the standard merge algorithm incurs a substantial slow-down. Virtual-Memory Powersort, by contrast, uses the same number of moves and comparisons as previous Powersort implementations up to an additive $O(n)$ term. We report on an empirical running-time study comparing our implementation against other Powersort variants and state-of-the-art stable sorting methods, demonstrating that almost in-place stable sorting can be achieved with negligible overhead in many scenarios.