Sorting real numbers in O(n n) time and linear space

DOI10.1007/S00453-019-00626-0MaRDI QIDQ2300729zbMATH OpenOpenAlexFDO

Authors Yijie Han

Publication date 28 February 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.00776

zbMATH Keywords

analysis of algorithmscomparison sortinginteger sortingsortingsorting real numbers

Mathematics Subject Classification ID

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

Abstract: We present an $O(nsqrtlogn)$ time and linear space algorithm for sorting real numbers. This breaks the long time illusion that real numbers have to be sorted by comparison sorting and take $Omega(nlogn)$ time to be sorted.

Recommendations

• Sorting numbers in linear expected time and optimal extra space
• Deterministic sorting in O(nloglogn) time and linear space
• Sorting in linear time?
• Improved fast integer sorting in linear space
• scientific article; zbMATH DE number 1263219

Cites work

• A Linear Time Algorithm for Ordered Partition
• Deterministic sorting in O(nloglogn) time and linear space
• scientific article; zbMATH DE number 4131650 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• In Praise of Numerical Computation
• Introduction to algorithms.
• Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs
• Tight(er) worst-case bounds on dynamic searching and priority queues
• Upper bounds for sorting integers on random access machines

Cited in

(4)

• Sorting numbers in linear expected time and optimal extra space
• When can we sort in o(n n) time?
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism

This page was built for publication: Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space

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