Lecture Notes On The New AKS Sorting Network

Ajtai, Koml'os, and Szemer'edi constructed sorting networks with N wires of depth O(log N ). They were not concerned with the value of the proportionality constant implicit in the O-notation; subsequently Paterson replaced the O(log N) by c log 2 N with c under 6100. We describe an implementation of a more recent, and as yet unpublished, proposal of Ajtai, Koml'os, and Szemer'edi, 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 log 2 N 0 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)) log M N + 115 as M ! 1. (It is ..