In section 4.3 we showed how procedure ODD-EVEN TRANSPOSITION can be modified so that its cost becomes optimal. Show that it is possible to obtain a cost-optimal sorting algorithm on the linear array...

In section 4.3 we showed how procedure ODD-EVEN TRANSPOSITION can be modified so that its cost becomes optimal. Show that it is possible to obtain a cost-optimal sorting algorithm on the linear array for the case of sequential input. One approach to consider is the following. For a sequence of length n, the linear array consists of I + log n processors. The leftmost processor receives the input, the rightmost produces the output. Each processor is connected to its neighbors by two lines, as shown in Fig. 4.9 for n = 8. This array can be made to sort in 0(n) time by implementing an adapted version of the sequential procedure Mergesort. This procedure consists of log n stages. In stage i sorted subsequences of length 2' are created, i = 1, 2_ ., log n. In the parallel adaptation, the steps are run overlapped on the linear array.