**Proof:**
The algorithm for sorting packets on an -node butterfly uses the algorithm for sorting
packets as a subroutine. First each packet independently chooses to
be a splitter with probability . With high
probability, this leaves candidates. The
candidates are sorted using the subroutine. Then every th
candidate is selected to be a splitter, leaving
splitters. The splitters are
distributed throughout the butterfly, and splitter-directed routing is
used to route intervals of size to
subbutterflies with inputs. Now each
interval of packets resides in a group of
butterfly rows. Each of these rows
contains packets. The packets in each row can be sorted
in time using an odd-even transposition sort [17, Section
1.6.1,]. With a
fixed number of row sorts and permutations, all of the packets in each
interval can be sorted in time using Columnsort.

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996