Comparison Networks

A comparison network is made of wires and comparators. A comparator is a device with two inputs, x and y, and two outputs, x' and y,' where

x'= min (x, y)
y' = max (x, y)

In Comparison Networks input appear on the left and outputs on the right, with the smallest input value appearing on the top output and the largest input value appearing on the bottom output. Each comparator operates in O (1) time. In other words, we consider that the time between the appearance of the input values x and y and the production of the output values x' and y' is a constant.

A wire transmits a value from place to place. A comparison network contains n input wires a₁,a₂,........a_n through which the benefits to be sorted enter the network, and n output wires b₁,b₂,......b_n which produce the results computed by the network.

Comparison Network is a set of comparators interconnected by wires. Running time of comparator can define regarding depth.

Depth of a Wire: An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths d_x and d_y' then its output wires have depth max (d_x,d_y) + 1.

A sorting network is a comparison network for which the output sequence is monotonically increasing (that is b₁≤ b₂ ≤ ....b_n) for every input sequence.

Fig: A Sorting network based on Insertion Sort