1. Improved average complexity for comparison-based sorting.
- Author
-
Iwama, Kazuo and Teruyama, Junichi
- Subjects
- *
MATHEMATICAL analysis - Abstract
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg n − 1.4427 n + O (log n). For many efficient algorithms, the first n lg n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is "two-element insertion," which inserts two elements A and B , A < B , into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach together with the binary insertion. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF