On the average case of MergeInsertion

DOI10.1007/S00224-020-09987-4MaRDI QIDQ5918284zbMATH OpenOpenAlexFDO

Authors Florian Stober, Armin Weiß

Publication date 11 June 2021

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-020-09987-4

zbMATH Keywords

average-case analysisMergeInsertionminimum-comparison sort

Mathematics Subject Classification ID

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

Recommendations

• On the average case of MergeInsertion
• Small Complexity Gaps for Comparison-Based Sorting
• QuickXsort: efficient sorting with n n - 1.399n + o(n) comparisons on average

Cites work

• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• A Tournament Problem
• New results in minimum-comparison sorting
• QuickXsort: a fast sorting scheme in theory and practice
• QuickXsort: efficient sorting with n n - 1.399n + o(n) comparisons on average
• Significant improvements to the Ford-Johnson algorithm for sorting
• The Ford-Johnson algorithm still unbeaten for less than 47 elements
• The Ford-Johnson Sorting Algorithm Is Not Optimal

Cited in

(4)

• Average merge time: an intuitive interpretation
• On the average case of MergeInsertion
• Small Complexity Gaps for Comparison-Based Sorting
• A variant of the Ford-Johnson algorithm that is more space efficient

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: On the average case of MergeInsertion

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