The butterfly sorting result from Section 8 does not directly extend to the shuffle-exchange graph because the shuffle-exchange graph does not have the nice recursive structure possessed by the butterfly. However we can use the following theorem to sort on the shuffle-exchange graph. A similar theorem was proven independently by Raghunathan and Saran [28].

**Proof:**
We assume that . Thus each row of each
butterfly can be represented by a *k*-bit string, and each node of
the shuffle-exchange can be represented by a *2k*-bit string.

To map butterflies to the shuffle-exchange graph, we use the following lemma [15, Lemma 1-1,].

For each of these subsets we pick the lexicographically minimum string
to represent the subset. We associate the butterflies in
a two to one fashion with the representative strings. Suppose
butterfly *i* is associated with string . We map a node in butterfly *i* to a shuffle-exchange node by shuffling
the bits of with the bits of *r*'s representation, and choosing
the current bit to be . That is, node in butterfly *i* is mapped to shuffle-exchange node
.

From a shuffle-exchange node we can recover the representative string by picking out every other bit and shifting to the lexicographically minimum string. We find the row string by picking out the other bits and shifting by the same amount. The position in the row is clearly the number of shifts we used to get to and the row number.

To finish, we observe that each edge in any of the butterflies is mapped to a path of length at most three in the shuffle-exchange graph since we either shift twice to reach 's image, or we exchange the current bit and shift twice to reach 's image.

Thus we can embed ( )-node butterflies in an *N*-node shuffle-exchange with
load 2, congestion , and dilation 3.

to .667emto .667em

This technique can be extended to prove that for any constant , distinct -node butterfly
graphs can be embedded in an *N*-node shuffle-exchange with constant
load, congestion, and dilation.

The following theorem shows that we can use Theorem 9.1 to sort on the shuffle-exhange graph in steps.

**Proof:**
The *N* packets can be sorted using the Columnsort algorithm
of [16]. Using Theorem 9.1, -node butterflies are embedded in the
shuffle-exchange graph with constant load, congestion, and dilation,
where . Each of the butterflies can sort packets in
time using the butterfly sorting algorithm of
Section 8. Columnsort sorts all *N* packets
using a constant number of butterfly sorting steps and global
permutation routing steps on the shuffle-exchange graph, each of which
takes time, with high probability.

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996