A space efficient distributive sort (Q758207): Difference between revisions

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)].