Next: 11 Remarks Up: Randomized Routing and Sorting Previous: 9 Sorting on shuffle-exchange

# 10 Sorting on multidimensional arrays

In this section we describe an algorithm for sorting kN packets on an N-node k-dimensional array with maximum side length M in steps. The algorithm closely follows the algorithm of Section 8 for sorting on the butterfly network. For the sake of brevity, we omit many of the details.

Sketch of proof: The algorithm is essentially the same as the algorithm for sorting on the butterfly. For simplicity, we assume that .

As before, there is a recursive subroutine for sorting packets. We describe the action of the subroutine on a -dimensional subcube. (A -dimensional subcube of an array is a subgraph of the array consisting of nodes whose labels share the same value in some set of coordinates. For example, given a set coordinates and a set of values, there is a subcube consisting of those nodes such that for .) The array is lightly loaded by the factor of to ensure that at each level of the recursion, the number of packets entering any -dimensional subcube is at most .

The first step is to choose a set of splitters. A set of packets are randomly chosen to be splitter candidates and then sorted by comparing every candidate with every other candidate, which can be done in steps. Next, every th candidate is selected to be a splitter.

The subcube routes packets on a leveled logical routing network as described in Section 6. The splitters are placed on the plateaus of the logical network, of them on plateau i. Since there are only splitters, only the first plateaus get any, where is some fixed constant less than one. On plateau 1, the jth splitter is assigned to all of the nodes labeled , where for . A packet routes across dimension 1 edges on plateau 1 until until it reaches a splitter that is larger than itself. It then routes across dimension 2 edges to plateau 2. Because dimension 1 edges do not appear in any later plateaus, each of the M intervals is routed to a disjoint k-1 dimensional subgraph of the logical network. On each of these subgraphs, M splitters are positioned on plateau 2, and so on.

The subroutine calls itself recursively on subcubes with dimensions. The recursion terminates when the number of packets entering a subcube is less than kM, in which case they are sorted sequentially in time. There are levels to the recursion. As before, we can estimate the time required by the algorithm by assuming that the time spent on a -dimensional subcube is equal to the expectation, . The time is given by the recurrence

which has solution . To rigorously bound the time we would have to argue that delay does accumulate across the levels of the recursion.

The algorithm for sorting kN packets calls the subroutine once. First, packets are randomly chosen to be candidates and sorted using the subroutine. Next, every th candidate is selected to be a splitter. The splitters partition the packets into intervals of size . Since , each interval has at most packets. Since the 1-dimensional subcubes can each sort kM packets in steps using bubblesort, and , Columnsort can be applied to sort all of the packets in steps.

to .667emto .667em

Next: 11 Remarks Up: Randomized Routing and Sorting Previous: 9 Sorting on shuffle-exchange

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996