Consider two sequences of numbers that are ordered, largest to smallest:
100 80 65 30 90 85 50 10
They may be merged to produce a new sequence containing all the numbers in order. For example, compare the two largest and place the larger one first in the final sequence. Continue comparing the two current largest and placing the larger in the next spot in the final sequence until all numbers have been placed. The result, of course, is
100 90 85 80 65 50 30 10
This merging algorithm takes 2n basic operations when there are n numbers in each original sequence. It is possible to merge the sequences using a different algorithm, which, when parallel processing is possible, can reduce the time to O(lg 2n) rather than O(2n) when n is a power of 2. It is not obvious how to do this. The solution involves
1. A "perfect shuffle" operation, for which we next develop a program
2. A compare-and-exchange operation, which we will discuss after the perfect shuffle
3.9.2 Array Implementation of the Perfect Shuffle
3.9.3 List Implementation of the Perfect Shuffle
3.9.4 Merging Sequences of Entries