2017/05/02 by Kazuo Iwama, Iwama, Kazuo, Junichi Teruyama +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.1705.00849
openalex publication_date 2017/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n \lg n - 1.4427n + 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 numbers A and B, A<b></b>