Algorithm

In our solution, we use two rounds of the transpose collective communication primitive. In the first round, each element is routed to an intermediate destination, and during the second round, it is routed to its final destination.

The pseudocode for our algorithm is as follows:

• Step (1): Each processor , for , assigns its elements to one of p bins according to the following rule: if element k is the first occurrence of an element with destination j, then it is placed into bin . Otherwise, if the last element with destination j was placed in bin b, then element k is placed into bin .
• Step (2): Each processor routes the contents of bin j to processor , for . Since we established that no bin can have more than elements [4], this is equivalent to performing a transpose communication primitive with block size .
• Step (3): Each processor rearranges the elements received in Step (2) into bins according to each element's final destination.
• Step (4): Each processor routes the contents of bin j to processor , for . Since we established that no bin can have more than elements [4], this is equivalent to performing a transpose primitive with block size .

The overall complexity of our algorithm is , which is asymptotically optimal with very small constants for .