Now that the perfect shuffle has been developed, let's return to the merging of two sequences. Set the first n entries of configuration to one of the sequences to be merged, and the second n entries of configuration to the other, but enter the second in reverse order.
Consider the following algorithm for merging two sequences of ordered (largest to smallest) entries, each of length n:
Apply perfectshuffle and compareexchange to configuration a total of 2n times.
Compareexchange is a function that compares each of the n pairs of adjacent configuration entries and exchanges their values whenever the second is larger than the first. Table 3.3 shows the results obtained as this algorithm is applied to our sample sequences of length 4. Since lg 2n = lg 8 = 3, the algorithm terminates after the third perfect shuffle and compare-and-exchange operation. Notice that this results in configuration containing the correct merged sequence.
When 2n is a power of 2, say 2k, then the k iterations always produce the correct merge. This is certainly not obvious, and it is not proven here, but one point is important. If this merge is implemented as a for loop and carried out conventionally (that is, sequentially), it will take time O(n lg n). The straightforward sequential merge discussed earlier takes only O(n) time. However, if the n moves of perfectshuffle and the n pair comparisons and interchanges of compareexchange are all done in parallel (at the same time), then the total time will be just O(lg n).
Parallel processing is beyond the scope of this text, but this application illustrates its power and some of the difficulties involved. Doing parallel processing correctly is tricky, since care must be taken to do the right thing at the right time. For instance, one could dress in parallel fashion, but certain constraints must be observed. Socks and shirt can be put on at the same time (a valet is needed of course, since a person has only two hands) followed by pants, with shoes and jacket next and in parallel. But shoes cannot go on before socks.
The perfect shuffle (and the topic of parallel processing) is pursued further in Stone [1971, 1980] and Ben-Ari [1982]. An application of these ideas to the stable marriage problem appears in Hull [1984].
Table 3.3 The Result of Merging Two Sequences of Ordered Entries of Length 4
Initial After First After First After Second
Configuration Perfect Shuffle Compare Exchange Perfect Shulle
-----------------------------------------------------------------
100 100 100 100
80 10 10 85
65 80 80 10
30 50 50 65
10 65 85 80
50 85 65 90
85 30 90 50
90 90 30 30
After Second After Third After Third
Compare Exchange Perfect Shuffle Compare Exchange
---------------------------------------------------
100 100 100
85 90 90
65 85 85
10 80 80
90 65 65
80 50 50
50 10 30
30 30 10