A space efficient distributive sort

DOI10.1016/0020-0190(91)90137-7MaRDI QIDQ758207zbMATH OpenOpenAlexFDO

Authors C. C. Handley

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0020-0190(91)90137-7

zbMATH Keywords

distributive sort

Mathematics Subject Classification ID

Searching and sorting (68P10) Distributed algorithms (68W15)

Review text

Distributive sorts operate by assigning each item to one of k buckets \((k=\lceil N/m\rceil\), \(1\leq m\leq 5)\). Typically they need k locations for bucket headers, plus N locations for the links, giving a total of \(N+N\lceil N/m\rceil\). Many methods (e.g. Uniform Sort \textit{D. C. S. Allison}, \textit{M. T. Noga} [BIT 22, 135-139 (1982; Zbl 0482.68055)]) copy the elements to intermediate storage and thus require a total of \(2N+\lceil N/m\rceil\) extra space. To minimise the incidence of empty buckets m is usually 2, so these methods use 1.5 N or 2.5 N extra locations. In comparison, the new algorithm requires only 0.5 N extra locations \((m=2)\). This algorithm is an attempt to combine the speed of Uniform sort loc. cit. with the space efficiency of Clocksort \textit{C. C. Handley} [An in situ distributive sort, Inf. Process. Lett. 23, 265-270 (1986)].

Recommendations

• An Internal Hybrid Sort Algorithm Revisited
• Sorting multisets stably in minimum space
• An analysis and implementation of an efficient in-place bucket sort
• Analyzing a class of distributive partitioning sort algorithms
• In-place linear probing sort

Cites work

• An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting
• Implementing Quicksort programs
• Sorting by distributive partitioning
• Sorting in linear expected time
• Sorting numbers in linear expected time and optimal extra space
• Usort: An efficient hybrid of distributive partitioning sorting

Cited in

(3)

• An analysis and implementation of an efficient in-place bucket sort
• An Internal Hybrid Sort Algorithm Revisited
• scientific article; zbMATH DE number 2247679 (Why is no real title available?)

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: A space efficient distributive sort

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