Adaptive sorting achieves faster results using new entropy measures
Adaptive Sorting, also in the BST Model
Data Structures and Algorithms
Summary
Sorting means putting things like a list of numbers in order, and some lists are easier to sort than others. The authors study different ways to measure how ‘easy’ a list is to sort, based on something called entropy. They show relationships among these measures and present new algorithms that sort faster when the list is easier. Their new sorting method, called SproutSort, works well inside a model called a binary search tree and adapts efficiently to the list’s structure. They also offer a simpler randomized sorting algorithm, SkeletonSort, which achieves similar speed for certain kinds of lists.
What this means in practice
- •For software engineers: Implement sorting routines that adapt efficiently to the input's inherent order, reducing average sorting time in many practical scenarios.
- •For data structure developers: Design binary search tree-based systems with better adaptive sorting capabilities using the SproutSort algorithm.
Authors
Ivor van der Hoog, Eva Rotenberg, Daniel Rutschmann
Abstract
Sorting is one of the most basic algorithmic problems. Adaptive sorting algorithms exploit features that make an input easier to sort, often captured by entropy measures. Many such measures have been studied, raising two natural questions: how do they relate to one another, and are there algorithms that are adaptive to them? We complete a hierarchy of relations between previously studied entropy measures and show that the classical measure Reg is a source of this hierarchy. We prove that an existing data structure yields a Reg-adaptive sorting algorithm, thereby achieving the adaptive bounds of every measure in the hierarchy. Following McIlroy's observation that Reg has a mathematically inconvenient definition, we study a slightly weaker but simpler measure, reg. For inputs without duplicates, we show that O(n + log reg) = O(n + log Reg), so this simplification preserves the adaptive bound. Finally, we do algorithms design and introduce SproutSort, a reg-adaptive algorithm in the offline binary search tree (BST) model. SproutSort achieves an access cost of O(n + log reg), making it the most adaptive algorithm in this model to date. We also introduce SkeletonSort, a simple randomised pointer-machine algorithm that sorts distinct keys in expected O(n + log reg) time, offering a considerably simpler implementation of a sorting algorithm this high in the adaptive hierarchy.