AbstractAjtai, Komlós, and Szemerédi constructed sorting networks with N wires of depth O(logN). They were not concerned with the value of the proportionality constant implicit in the O-notation; subsequently Paterson replaced the O(logN) by c log2 N with c under 6100. We describe an implementation of a more recent, and as yet unpublished, proposal of Ajtai, Komlós, and Szemerédi, that yields a smaller value of c: for every integer N such that N >= 2^78 there is a sorting network on N wires whose depth is at most 1830 log2 N - 58657. The basic units in this new construction are sorting networks on M wires such that M is relatively small; these may be thought of as indivisible hardware elements (rather than networks made from comparators); following Knuth, we call them M-sorters. For every choice of positive integers M and N such that N >= M, the construction yields a sorting network on N wires, made from M-sorters, whose depth is at most (48 + o(1)) logM N + 115 as M --> ∞. (It is worth emphasizing that the asymptotic o(1) here is relative to M rather than N.)
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).