Towards universally optimal sorting algorithms

Sandeep Sen

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. W…