查看文章

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 2nlogI/n + O(n) [1]. The bound on the number of comparisons is further reduced to 1.89nlogI/n + O(n) by using a new structure, which we call trinomial queues. The fact that the algorithm is simple and relies on fairly simple structures makes it a good candidate in practice.