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.