O'Reilly logo

Art of Computer Programming, The: Volume 3: Sorting and Searching by Donald E. Knuth

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

*5.3.4. Networks for Sorting

In this section we shall study a constrained type of sorting that is particularly interesting because of its applications and its rich underlying theory. The new constraint is to insist on an oblivious sequence of comparisons, in the sense that whenever we compare Ki versus Kj the subsequent comparisons for the case Ki < Kj are exactly the same as for the case Ki > Kj, but with i and j interchanged.

Figure 43(a) shows a comparison tree in which this homogeneity condition is satisfied. Notice that every level has the same number of comparisons, so there are 2m outcomes after m comparisons have been made. But n! is not a power of 2; some of the comparisons must therefore be redundant, in the sense that one of their ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required