2. Batcher Sorting Network A comparator is a device which sorts two numbers r and y, as shown in Figure 1. inputs outputs min(x,y) max(x,y) Figure 2: a comparator The Batcher sorting network was presented in class. It is constructed with a block called the Merge network. Given two sorted input sequences xo, ri,... , Tn/2-1 and ,T1 , . . . , zn/2-1 The recursive construction of the Merge [8] network is shown in Figure 3. The re- cursive construction of the Batcher [8] network, based on the Merge [8] network, is shown in Figure 4. The Merge [2] and Batcher [2] networks both consist of a single balancer , the Merge [n] network produces a sorted output sequence Yo, y!' .. , yn-l inputs outputs Merge[4] Merge[4] Figure 3: the Merge [8] network (a) What is the depth of the Merge [8] network? The Batcher [16] network? The depth of a Batcher [321 network? (b) Draw Batcher [32] network