On the upper bound of the complexity of sorting

DOI10.1134/S0965542521020111MaRDI QIDQ2662813zbMATH OpenOpenAlexFDO

Authors I. S. Sergeev

Publication date 15 April 2021

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0965542521020111

zbMATH Keywords

complexitydecision treepartial ordersimplexsorting

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A Tournament Problem
• Finding the median
• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Merging of 4 or 5 elements with n elements
• Optimal merging of 2 elements with n elements
• QuickXsort: a fast sorting scheme in theory and practice
• Selecting the Median
• The Ford-Johnson algorithm still unbeaten for less than 47 elements

Cited in

(8)

• Upper bounds for time-space trade-offs in sorting and selection
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• Untangling upper-bound sieves
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• scientific article; zbMATH DE number 1827438 (Why is no real title available?)
• On the Complexity of Approximate Sum of Sorted List
• scientific article; zbMATH DE number 5182609 (Why is no real title available?)
• Lower bound techniques in the comparison-query model and applications to inversion minimization

This page was built for publication: On the upper bound of the complexity of sorting

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