next up previous
Next: 9 Sorting on shuffle-exchange Up: 8 Sorting on butterflies Previous: 8.5 Bounding the cumulative

8.6 Putting it all together


Proof: The algorithm for sorting tex2html_wrap_inline4361 packets on an tex2html_wrap_inline4363 -node butterfly uses the algorithm for sorting tex2html_wrap_inline4365 packets as a subroutine. First each packet independently chooses to be a splitter with probability tex2html_wrap_inline4367 . With high probability, this leaves tex2html_wrap_inline4369 candidates. The candidates are sorted using the subroutine. Then every tex2html_wrap_inline4371 th candidate is selected to be a splitter, leaving tex2html_wrap_inline4373 splitters. The splitters are distributed throughout the butterfly, and splitter-directed routing is used to route intervals of size tex2html_wrap_inline4375 to subbutterflies with tex2html_wrap_inline4377 inputs. Now each interval of tex2html_wrap_inline4379 packets resides in a group of tex2html_wrap_inline4381 butterfly rows. Each of these rows contains tex2html_wrap_inline4383 packets. The packets in each row can be sorted in tex2html_wrap_inline4385 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 tex2html_wrap_inline4387 time using Columnsort.

to .667emto .667em

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