File SortingNetworks.h

↰ Parent directory (ADS/sort)

Sorting networks, beyond the book: sequences of comparators ( i , j ), i != j, each putting the smaller of A[ i ] and A[ j ] in A[ i ], fixed in advance whatever the input, so that the comparators of a round touch disjoint places and run in parallel (in hardware, on SIMD lanes, on a GPU):

Definition (ADS/sort/SortingNetworks.h)

Detailed Description

  • mergeExchangeNetwork() is the merge exchange of Batcher (Algorithm M of Knuth) for any n, :math:` O( n log^2 n ) ` comparators in :math:` O( log^2 n ) ` rounds;

  • bitonicNetwork() is the bitonic sorter of Batcher for n a power of 2: two halves sorted in opposite directions form a bitonic sequence, which a half-cleaner splits into two bitonic halves, every item of the first not larger than every item of the second; also :math:` O( n log^2 n ) ` comparators;

  • applyNetwork() runs a network on a vector, and the 0-1 principle (a network sorts every input if it sorts every input of 0 and 1) is what the tests check.

The contracts [see File Contract.h]: the comparators of a network join two distinct places within n, a bitonic network needs n a power of 2, and applyNetwork() a vector of at least n items. The functions are defined in SortingNetworks.tpp.

    1. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307-314, 1968, doi:10.1145/1468075.1468121

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, sections 5.2.2 (Algorithm M) and 5.3.4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs