Constant-time sorting

DOI10.1016/J.IC.2014.01.017MaRDI QIDQ2252525zbMATH OpenOpenAlexFDO

Authors Michael Brand

Publication date 18 July 2014

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2014.01.017

zbMATH Keywords

arithmetic complexityrandom access machinesorting

Mathematics Subject Classification ID

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

Recommendations

• Constant time parallel sorting: An empirical view.
• Sorting in linear expected time
• LATIN 2004: Theoretical Informatics
• Optimal incremental sorting
• Deterministic sorting in O(nloglogn) time and linear space
• Time-complexity of shear sort
• scientific article; zbMATH DE number 2119639
• Constant time sorting on a processor array with a reconfigurable bus system

Cites work

• Computer arithmetic algorithms.
• Computing with and without arbitrary large numbers
• Deterministic sorting in O(nloglogn) time and linear space
• Division in idealized unit cost RAMs
• Does indirect addressing matter?
• scientific article; zbMATH DE number 3653573 (Why is no real title available?)
• scientific article; zbMATH DE number 3757704 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• Lower Bounds for Sorting with Realistic Instruction Sets
• On the power of the shift instruction
• Upper bounds for sorting integers on random access machines

Cited in

(3)

• P-RAM vs. RP-RAM
• Purely Functional Worst Case Constant Time Catenable Sorted Lists
• LATIN 2004: Theoretical Informatics

This page was built for publication: Constant-time sorting

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