On the average case of MergeInsertion

DOI10.1007/S00224-020-09987-4zbMath1503.68055OpenAlexW2957201506MaRDI QIDQ5918284

Florian Stober, Armin Weiß

Publication date: 11 June 2021

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

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

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

Uses Software

• GitHub

Cites Work

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

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