TAOCP 5.3.4 Exercise 5
The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison...
Section 5.3.4: Networks for Sorting
Exercise 5. [**] [M16] Prove that (13) is the delay time associated with the sorting network outlined in (10).
Verified: yes
Solve time: 1m05s
The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison-interchanges given in (1). The two recursive subnetworks operate on disjoint sets of wires, so their execution can be performed in parallel. The delay contributed by the recursive stage is therefore the maximum of the delays of the two subproblems, namely $T_g(\lceil m/2\rceil,\lceil n/2\rceil)$ and $T_g(\lfloor m/2\rfloor,\lfloor n/2\rfloor)$.
After both subnetworks complete, the final layer (1) consists of a single additional stage of comparators, each acting independently on adjacent outputs of the interleaved sequence (2). This stage increases the critical path length by exactly one unit. Hence the delay recurrence for the odd-even merge network is
$T_g(m,n)=\max!\bigl(T_g(\lceil m/2\rceil,\lceil n/2\rceil),,T_g(\lfloor m/2\rfloor,\lfloor n/2\rfloor)\bigr)+1,$
with the same boundary conditions as in (10). This coincides with the delay equation stated in (13), so (13) correctly describes the delay time of the network defined in (10). This completes the proof. ∎