Sorting numbers in linear expected time and optimal extra space

DOI10.1016/0020-0190(82)90043-6MaRDI QIDQ1167543zbMATH OpenOpenAlexFDO

Authors Teofilo F. Gonzalez, Donald B. Johnson

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90043-6

zbMATH Keywords

sorting randomly selected numbers

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• Sorting in linear time?
• scientific article; zbMATH DE number 1629826
• scientific article; zbMATH DE number 140497
• scientific article; zbMATH DE number 1263219

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Implementing Quicksort programs
• Internal Sorting by Radix Plus Sifting
• Quicksort
• Searching and sorting real numbers
• Sorting by distributive partitioning
• The analysis of Quicksort programs
• The design and analysis of a new hybrid sorting algorithm

Cited in

(10)

• In-place linear probing sort
• Radix Sorting with No Extra Space
• Sorting multisets stably in minimum space
• Sorting real numbers in \(O(n \sqrt{\log n})\) time and linear space
• scientific article; zbMATH DE number 411147 (Why is no real title available?)
• A space efficient distributive sort
• Improved fast integer sorting in linear space
• Sorting in linear expected time
• Sorting in linear time?
• Sorting multisets stably in minimum space

Describes a project that uses

Uses Software

• Quicksort
• Find
• heapsort

This page was built for publication: Sorting numbers in linear expected time and optimal extra space

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