Learning sorting networks by grammars
Thomas E. Kammeyer, Richard K. Belew · 1994
A compare-exchange network, or CMPX-net, is a se-quence of operations of the form [i: j], each of which operates on an array, D, of length N. The network is said to have width N. The length of the network is the number of CMPX’s in the network. For each [i: j], we have i O[j] for each [i: j] in the sequence. A sorting networlc(SNet) is a CMPX-net which will sort D’s contents into nonde-creasing order no matter how D’s contents are ordered initially. A merging network (MNet) is a pair contain-ing a CMPX-net of even width, N, and a partition of the indices into two equal-size sets or “sides. ” If the data on each side of the partition are sorted initially then the output will be sorted. The space of CMPX-