DIMACS TR: 2001-24

Optimal Adaptive Sorting

Authors: Amr Elmasry


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