scientific article; zbMATH DE number 5182609

MaRDI QIDQ5757092zbMATH OpenFDO

Authors Rachit Agarwal, Emanuel M. Popovici, K. L. Man, M. Schellekens

Publication date 24 August 2007

zbMATH Keywords

comparison-based algorithmssorting

Mathematics Subject Classification ID

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

• A simple proof of a time-space trade-off for sorting with linear comparisons
• A general lower bound on the I/O-complexity of comparison-based algorithms
• Tight Comparison Bounds on the Complexity of Parallel Sorting
• On the worst-case complexity of TimSort
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Area-time lower-bound techniques with applications to sorting
• On the upper bound of the complexity of sorting
• Small Complexity Gaps for Comparison-Based Sorting

Cited in

(5)

• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• New results in minimum-comparison sorting
• Comparing algorithms for sorting with t stacks in series
• \texttt{tttplots-compare}: a Perl program to compare time-to-target plots or general runtime distributions of randomized algorithms
• Linear-time in-place selection in less than 3n comparisons

This page was built for publication:

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