AlgorithmsAdvanced~120 min

GPU Radix Sort

Build a fully parallel LSD radix sort on the GPU. Implement digit histogram, exclusive scan for scatter addresses, and the scatter kernel.

radix-sortscanscatterhistogramthrust

// PROJECT PHASES

  1. 1

    Single-bit split

    Sort by one bit at a time.

  2. 2

    4-bit digit histogram and scan

    16-bucket histogram per block.

  3. 3

    Scatter pass

    Write keys to their sorted positions.

  4. 4

    Full 32-bit sort (8 passes)

    Chain 8 passes, ping-pong buffers.

// SANDBOX

GPU execution
main.cu
loading editor…

// EXPECTED OUTPUT

Radix sort (1M keys):   4.2 ms
Result sorted correctly: YES

// YOUR PROGRESS

Log in to save progress

// DETAILS

Category
Algorithms
Difficulty
Advanced
Est. time
~120 min
Prerequisites
2

// LEARN THE THEORY

Algorithms concepts