Constant-time parallel integer sorting
Torben Hagerup · 1991
We investigate a nonstandard output convention for sorting.Specifically, the input elements are to be returned not in an array sorted in nondecrea.singorder, but in a linked list sorted in nondecreasing order.This problem, which we call chuin-sorting, may be viewed as standard sorting "minus" list ranking, the elements of Bi in this bucket through a random "dart throwing" process.The third part is similar to ordered chaining.The same three parts can be distinguished in the algorithms of (Rajasekaran and Reif, 1989).Whenever we speak of randomly choosing an element from a set without explicitly mentioning a probability distribution, the uniform distribution over the relevant set is to be understood.Form61Nand V~{l ,..., m}, define MAXGAPm(V) as the size of the largest set disjoint from V and of the form {a, . ...b} or {b, . ...m. l,a}, ,a}, where a, bE {l,... ,m}, ora8zeroif V= {l,... ,rn}.Fact 1: Let m and k be integers with 1 < k < m and let V be a set chosen randomly from the uniform distribution over all k-element subsets of {1,..., m}.Then for every r ~O, Pr(MAXGAPm(V) ~?') ~me-rkJm.Fact 2 (Chernoff bounds): For every binomially distributed random variable S, (a) Pr(S ~2E(S)) ~e-~is)i'; (b) Pr(S < 17( S)/2) ~e-E(s)i8; (c) For every r ~6.E(S), Pr(S ~r) ~2-".Fact 3: Let m, S,V E IN and let 21,1, . .., Zm,V be independent and uniformly