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.