## DIMACS TR: 2001-24

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.