Parallel Sorting

Parallel Sorting Algorithms — sorting large datasets across multiple cores or GPUs, where traditional sequential sorts (quicksort, mergesort) must be redesigned to exploit parallelism.

Key Parallel Sorting Approaches

1. Parallel Merge Sort
- Recursively divide array, sort halves in parallel, merge
- Merge step is the bottleneck (inherently sequential in naive form)
- Parallel merge: Split merge into independent sub-problems
- Complexity: O(n log n / p + n) with p processors

2. Bitonic Sort
- Network-based sort with O(log²n) parallel steps
- Each step: Compare-and-swap independent pairs → highly parallel
- Popular on GPUs: Fixed communication pattern maps well to GPU architecture
- CUB/Thrust library: `thrust::sort()` uses radix sort internally

3. Parallel Radix Sort
- Most practical GPU sort algorithm
- Process digits from LSB to MSB, each pass is a parallel scan + scatter
- Complexity: O(k × n/p) where k = number of digit passes
- CUB DeviceRadixSort: Sorts billions of keys per second on modern GPUs

4. Sample Sort
- Choose p-1 splitters to partition data into p roughly equal buckets
- Distribute buckets to processors, each sorts locally
- Good for distributed memory systems (MPI)

GPU Sort Performance

• NVIDIA H100: ~50 billion 32-bit keys/second
• 100x faster than single-core CPU sort
• Thrust/CUB provides production-quality implementations

Parallel sorting is a fundamental primitive — it underpins database operations, graphics rendering, and distributed data processing.