parallel sorting algorithm

**Parallel Sorting Algorithms** are the **class of sorting algorithms designed to exploit multiple processors or GPU cores to sort N elements in O(N log N / P) time on P processors — where the choice between comparison-based (merge sort, bitonic sort) and non-comparison (radix sort) approaches, combined with the hardware architecture (GPU, multi-core CPU, distributed cluster), determines real-world sorting throughput**. **GPU Sorting: Radix Sort Dominates** For integer and floating-point keys, parallel radix sort is the fastest algorithm on GPUs. CUB and Thrust's radix sort routinely achieves >10 billion keys/second on modern GPUs (A100/H100). **Radix Sort (GPU)**: 1. Process one digit (4-8 bits) at a time, from least significant to most significant. 2. For each digit: compute a histogram of digit values across all elements (parallel histogram), perform an exclusive scan on the histogram to compute output positions, scatter elements to their new positions. 3. Repeat for all digits (8 passes for 32-bit keys with 4-bit digits, or 4 passes with 8-bit digits). 4. Each pass is O(N) work, fully parallelizable. Total: O(k × N) where k = key_bits / digit_bits. **Bitonic Sort (GPU)**: A comparison-based sorting network that works by recursively building bitonic sequences (sequences that first increase then decrease) and merging them. Fixed communication pattern (independent of data) makes it ideal for GPU implementation — no data-dependent branching. Performance: O(N log²N) comparisons. Used when stable sort is not required and key comparison is the only option. **Merge Sort (Multi-Core CPU / Distributed)**: - Each processor sorts its local chunk independently (quicksort or introsort). - Pairwise merge phases combine sorted chunks. For P processors: log2(P) merge rounds. - Distributed merge sort is the standard for sorting beyond single-machine capacity (TeraSort benchmark). - Sample sort variant: draw random samples to estimate splitters, partition data by splitter ranges, sort each partition independently. Better load balance than simple merge sort. **Sorting in Distributed Systems** - **Sample Sort**: All processors sample their local data. Samples are gathered, sorted, and P-1 splitters are selected. Each processor partitions its data by the splitters and sends each partition to the responsible processor. Each processor sorts its received data. Near-optimal load balancing with high probability. - **Sorting Networks**: Deterministic algorithms like AKS network or Batcher's bitonic network with fixed comparison/exchange patterns. Useful when the communication pattern must be predetermined. Parallel Sorting is **the benchmark by which parallel algorithm engineers measure their hardware and software stack** — because sorting's mix of computation, memory access, and communication exercise every aspect of a parallel system.