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.
DIMACS Home Page