Improved average complexity for comparison-based sorting

DOI10.1016/j.tcs.2019.06.032zbMath1436.68087arXiv1705.00849OpenAlexW2611674041WikidataQ127495741 ScholiaQ127495741MaRDI QIDQ5919334

Kazuo Iwama, Junichi Teruyama

Publication date: 22 January 2020

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.00849

zbMATH Keywords

sortingaverage-case analysisbinary searchsorting algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (5)

On the upper bound of the complexity of sorting ⋮ Small Complexity Gaps for Comparison-Based Sorting ⋮ On the average case of MergeInsertion ⋮ QuickXsort: a fast sorting scheme in theory and practice ⋮ 2 mm: a new technique for sorting data

Cites Work

• The Ford-Johnson algorithm still unbeaten for less than 47 elements
• A variant of the Ford-Johnson algorithm that is more space efficient
• Merging of 4 or 5 elements with n elements
• New results in minimum-comparison sorting
• Optimal merging of 2 elements with n elements
• Tape-reversal bounded Turing machine computations
• Optimal expected-time algorithms for merging
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• The Ford-Johnson Sorting Algorithm Is Not Optimal
• QuickXsort: Efficient Sorting with n logn − 1.399n + o(n) Comparisons on Average
• A Tournament Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved average complexity for comparison-based sorting