作者
Amr Elmasry, Michael L Fredman
发表日期
2008/2
期刊
Acta Informatica
卷号
45
期号
1
页码范围
33-42
出版商
Springer-Verlag
简介
We present two algorithms that are near optimal with respect to the number of inversions present in the input. One of the algorithms is a variation of insertion sort, and the other is a variation of merge sort. The number of comparisons performed by our algorithms, on an input sequence of length n that has I inversions, is at most . Moreover, both algorithms have implementations that run in time . All previously published algorithms require at least comparisons for some c > 1.
引用总数
学术搜索中的文章
A Elmasry, ML Fredman - Acta Informatica, 2008
A Elmasry, ML Fredman - STACS 2003: 20th Annual Symposium on Theoretical …, 2003