Example of shuffle sort
Monday, March 01, 2010
4:46 PM
Understanding butterfly sort
Number processors 0-n. 
Map each key to hash h(k) between 0 and n. 
At step s (from 0  to log2(n)), 
if k is at processor p and h(k) differs from p in the sth bit, send <k,v> to processor p^(1<<s) (^=xor). 
Suppose key k is at worker 0=0002 and needs to be at worker 5=h(k)=1012 in binary
First worker 0=0002 sends it to worker 1 = 0012. 
Then worker 1=0012 sends it to worker 5 = 1012. 
Theorem: a key always gets to its intended destination in O(log(N)) steps, where N is the number of workers. 