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.