We introduce a technique called wire elimination
by which it is possible to remove wires and comparators
)-merging and n
-sorting circuits such that the
resulting circuits are (n'
)-merging and n'
circuits, resp., with n'
By neatly choosing the wires to be removed,
it is possible to obtain for n'
new circuits that have
size less than circuits previously designed for n'
We demonstrate this approach by
eliminating from the classical Bitonic (2n
wires such that an (n
which has 1/2 n
comparators less than the classical
)-merge circuit, but still the same depth.
Using the usual sorting by merging technique,
we get a variant of Bitonic sort
which saves 1/4 n
-1) comparators compared to the