Chapter 8

Comparison-Based In-Place Sorting with CUDA

Hagen Peters and Ole Schulz-Hildebrandt

Although there are many efficient sorting algorithms and implementations for graphics processing units (GPUs) (merge sort [1], radix sort [1, 2], sample sort [3], quick sort [4], …) none of them are both comparison-based and work in-place. The sorting algorithm presented in this chapter is a sorting algorithm for NVIDIA’s GPUs that is both comparison-based and works in-place. It outperforms all other comparison-based algorithms known to the authors (all of them working out of place) for a wide range of sequence lengths and key types. Furthermore, it is also competitive to noncomparison-based algorithms. Because this algorithm is based on sorting networks, ...

Get GPU Computing Gems Jade Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.