Abstract
Ajtai, 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.)