The size of a comparison network is the number of comparators, and the depth is the number of levels of comparators. For example, in the Wikipedia article, the initial sorting network for four inputs has size five and depth three. Notice that the first two comparators can execute simultaneously, so they are actually at the same level. The parallel bubble sort network for six inputs has size fifteen and depth nine. In general, a parallel bubble sort network for n inputs has size n(n − 1)/2 and depth 2n − 3. A minmax network inputs a list of size n and outputs a list of size n with the smallest value at the beginning of the list the largest value at the end of the list. For example if the input is the list of size n = 8

(40,80, 30, 60, 10, 70,20,50).

The output would be (10, ?, ?, ?, ?, ?, ?,80).

1. Let n be a power of 2.

a. Show how to construct an efficient minmax network with n inputs. Primarily minimize the depth and secondarily minimize the size. Just describe the network; do not justify.
b. What is the (exact) size of your network?
c. What is the (exact) depth of your network?