Parallel Merge Sort
Parallel Sorting Algorithms are the fundamental computational primitives that order N elements in O(N log N / P) time on P processors — where GPU-optimized sorts (radix sort, merge sort, bitonic sort) achieve throughputs of billions of keys per second by exploiting massive parallelism, coalesced memory access, and shared-memory-based local sorting to provide the ordered data that indexing, searching, database queries, and computational geometry require.
GPU Radix Sort — The Throughput Champion
Radix sort processes one digit (k bits) at a time from least significant to most significant:
1. Local Histogram: Each thread block computes a histogram of k-bit digit values for its tile of data. k=4 bits → 16 buckets.
2. Prefix Sum (Scan): Global scan of histograms computes output offsets for each digit bucket across all blocks.
3. Scatter: Each element is written to its computed output position based on its digit value and the prefix sum offset.
4. Repeat: For 32-bit keys with 4-bit digits: 8 passes. Each pass is O(N) — total is O(N × 32/k).
GPU radix sort achieves 5-10 billion 32-bit keys/second on modern GPUs (H100). CUB and Thrust provide highly optimized implementations.
Merge Sort — The Comparison-Based Champion
For arbitrary comparison functions (not just integers):
1. Block-Level Sort: Each thread block sorts its tile (1024-4096 elements) using sorting networks or insertion sort in shared memory.
2. Multi-Way Merge: Progressively merge sorted tiles into larger sorted sequences. GPU-optimized merge uses binary search to partition the merge task equally across threads — each thread determines which elements from the two input sequences belong to its output range.
3. Complexity: O(N log²N / P) for simple parallel merge; O(N log N / P) with optimal merge partitioning.
Bitonic Sort — The Network Sort
A comparison-based sorting network with fixed comparison pattern:
- Structure: Recursively builds bitonic sequences (first ascending, then descending), then merges them. log²N stages of parallel compare-and-swap operations.
- GPU Advantage: Fixed control flow — no data-dependent branches, perfect for SIMT execution. Every thread performs the same comparison pattern.
- Limitation: O(N log²N) work — not work-efficient. Best for small arrays (≤1M elements) or as a building block within merge sort for the final stages.
Performance Comparison
| Algorithm | Work | Depth | Best GPU Use |
|---|---|---|---|
| Radix Sort | O(N × b/k) | O(b/k × log N) | Integer/float keys, maximum throughput |
| Merge Sort | O(N log N) | O(log²N) | Custom comparators, stable sort |
| Bitonic Sort | O(N log²N) | O(log²N) | Small arrays, fixed-function sorting |
| Sample Sort | O(N log N) | O(log N) | Distributed memory, very large N |
Sorting as a Primitive
GPU sorts are building blocks for higher-level operations:
- Database query processing: ORDER BY, GROUP BY, JOIN (sort-merge join).
- Computational geometry: Spatial sorting for kd-tree construction, z-order curve computation.
- Rendering: Depth sorting for transparency, tile binning for rasterization.
- Stream compaction: Sort by predicate key, then take the prefix.
Parallel Sorting Algorithms are the throughput engines that transform unordered data into searchable, joinable, and analyzable form — the computational primitives whose GPU implementations process billions of records per second, enabling real-time analytics on datasets that sequential sorting would take minutes to process.