Back to Search
Start Over
Improved average complexity for comparison-based sorting.
- Source :
-
Theoretical Computer Science . Feb2020, Vol. 807, p201-219. 19p. - Publication Year :
- 2020
-
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]
- Subjects :
- *MATHEMATICAL analysis
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 807
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 141293271
- Full Text :
- https://doi.org/10.1016/j.tcs.2019.06.032