Showing 2026Show all
3 papers · 1 filter
cs.DS2026
Top-Down Mergesort with Sorted Check Has Mergecost
Sebastian Wild
We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be cor…
cs.DS2026
Virtual-Memory Powersort
Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild
We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption o…
cs.DS2026
Partition-based Simple Heaps
Gerth Stølting Brodal, John Iacono, Casper Moldrup Rysgaard +1
We introduce a new family of priority-queue data structures: partition-based simple heaps. The structures consist of doubly-linked lists; order is enforced among data i…