Small Complexity Gaps for Comparison-Based Sorting

DOI10.1007/978-3-319-98355-4_16MaRDI QIDQ6163631zbMATH OpenFDO

Authors Kazuo Iwama, Junichi Teruyama

Publication date 30 June 2023

Published in Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-98355-4_16

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• On the average case of MergeInsertion
• On the average case of MergeInsertion
• QuickXsort: efficient sorting with n n - 1.399n + o(n) comparisons on average

Cites work

• A Tournament Problem
• A variant of the Ford-Johnson algorithm that is more space efficient
• Counting linear extensions
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1947440 (Why is no real title available?)
• scientific article; zbMATH DE number 3062551 (Why is no real title available?)
• Merging of 4 or 5 elements with n elements
• New results in minimum-comparison sorting
• Optimal expected-time algorithms for merging
• Optimal merging of 2 elements with n elements
• QuickXsort: efficient sorting with n n - 1.399n + o(n) comparisons on average
• The Ford-Johnson algorithm still unbeaten for less than 47 elements
• The Ford-Johnson Sorting Algorithm Is Not Optimal

Cited in

(4)

• New results in minimum-comparison sorting
• scientific article; zbMATH DE number 5182609 (Why is no real title available?)
• On the average case of MergeInsertion
• On the average case of MergeInsertion

This page was built for publication: Small Complexity Gaps for Comparison-Based Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163631)