|
|
< Day Day Up > |
|
In Part II, we examined sorting algorithms for serial computers (random-access machines, or RAM's) that allow only one operation to be executed at a time. In this chapter, we investigate sorting algorithms based on a comparison-network model of computation, in which many comparison operations can be performed simultaneously.
Comparison networks differ from RAM's in two important respects. First, they can only perform comparisons. Thus, an algorithm such as counting sort (see Section 8.2) cannot be implemented on a comparison network. Second, unlike the RAM model, in which operations occur serially-that is, one after another-operations in a comparison network may occur at the same time, or "in parallel." As we shall see, this characteristic allows the construction of comparison networks that sort n values in sublinear time.
We begin in Section 27.1 by defining comparison networks and sorting networks. We also give a natural definition for the "running time" of a comparison network in terms of the depth of the network. Section 27.2 proves the "zero-one principle," which greatly eases the task of analyzing the correctness of sorting networks.
The efficient sorting network that we shall design is essentially a parallel version of the merge-sort algorithm from Section 2.3.1. Our construction will have three steps. Section 27.3 presents the design of a "bitonic" sorter that will be our basic building block. We modify the bitonic sorter slightly in Section 27.4 to produce a merging network that can merge two sorted sequences into one sorted sequence. Finally, in Section 27.5, we assemble these merging networks into a sorting network that can sort n values in O(lg2 n) time.
|
|
< Day Day Up > |
|