Parallel sorting pattern

• DOI: 10.1145/1953611.1953621
• Publication Date: 2011-04-01T11:55:37Z
• Authors: Vivek Kale; Edgar Solomonik
• Keywords: 0403 veterinary science; 04 agricultural and veterinary sciences

A large number of parallel applications contain a computationally intensive phase in which a large list of elements must be ordered based on some common attribute of the elements. How do we sort a sequence of elements on multiple processing units so as to minimize redistribution of keys while allowing processing units to do independent sorting work?