Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
Virtual-Memory Powersort reduces the memory consumption of adaptive mergesort from *n*/2 to *O*(√(*n* log *n*)) by employing internal buffering techniques. This is achieved while maintaining the same number of moves and comparisons as previous Powersort implementations, up to an additive *O*(*n*) term, avoiding the slowdown typically associated with in-place merging. Empirical results show that this near in-place stable sorting has negligible overhead in many scenarios compared to other Powersort variants and state-of-the-art stable sorting methods.
Powersort can now achieve near in-place stable sorting with minimal overhead, thanks to a novel virtual-memory implementation that slashes memory consumption.
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.