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