4 papers
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…
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…
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…
Towards Lazy B-Trees
Casper Moldrup Rysgaard, Sebastian Wild
Lazy search trees (Sandlund & Wild FOCS 2020, Sandlund & Zhang SODA 2022) are sorted dictionaries whose update and query performance smoothly interpolates between that of efficient…