high performance computing on graphics processing units: hgpu.org

Sorting and merging are two important kernels which are used as subroutines in numerous algorithms, whose performance depends on the efficiency of these primitives. Databases use sort and merge primitives extensively. Computational biology, search engines, realtime rendering and geographical information systems are other fields where sorting and merging large amounts of data is indispensable. Even when their great practical importance is taken aside; many interesting patterns arise in the design and engineering of sorting procedures, which can be applied to other types of algorithms [23]. More specifically, parallel sorting is a pervasive topic. Both sorting and merging are problems that lend themselves to parallelization. Numerous strategies have been designed that map sorting successfully to different kinds of processor architectures. Yet there are gaps between theory and practice. Coles parallel merge sort [11], for example, has optimal work complexity and step complexity. In practice, however, it is so far not competitive to simpler but theoretically worse algorithms [30]. Sorting networks have been researched since the 1960s [5]. While networks with lower asymptotic complexity are known [3], the 40 years old odd-even network and bitonic network are still in use today because they perform better in practice. Different sorting algorithms can be combined in countless ways into different sorting strategies. This makes parallel sorting a fruitful area for research from both a theoretical and practical point of view.