## DIMACS TR: 2001-24

## Optimal Adaptive Sorting

### Authors: Amr Elmasry

**
ABSTRACT
**

We introduce Binomialsort, an adaptive sorting algorithm that is optimal
with respect to the number of inversions. The number of comparisons
performed by Binomialsort, on an input sequence of length n that has I
inversions, is at most $2n \log{\frac{I}{n}} + O(n)$. The bound on the
number of comparisons is further reduced to $\frac{3}{\log{3}} n
\log{\frac{I}{n}} + O(n)$ by using a new structure, which we call
trinomial queues. Experimental results show that our sorting algorithm is
practical, efficient and easy to implement.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-24.ps.gz

DIMACS Home Page