Towards universally optimal sorting algorithms
By: Sandeep Sen
Potential Business Impact:
Makes computer sorting smarter by looking at more details.
We formalize a new paradigm for optimality of algorithms, that generalizes worst-case optimality based only on input-size to problem-dependent parameters including implicit ones. We re-visit some existing sorting algorithms from this perspective, and also present a novel measure of sortedness that leads to an optimal algorithm based on partition sort. This paradigm of measuring efficiency of algorithms looks promising for further interesting applications beyond the existing ones.
Similar Papers
Sorting as Gradient Flow on the Permutohedron
Data Structures and Algorithms
Sorts information faster by finding hidden patterns.
Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
Computational Geometry
Makes computer sorting faster by understanding data order.
Optimization of Base-n Radix Sort for Skewed Datasets
Data Structures and Algorithms
Sorts numbers faster, especially with many small ones.