parallel sorting algorithms

**Parallel Sorting Algorithms** are **sorting methods designed to exploit multiple processing elements simultaneously, distributing comparison and data movement operations across processors to achieve sub-linear time complexity relative to sequential sorting** — efficient parallel sorting is foundational for database operations, scientific computing, and GPU-accelerated data processing. **Bitonic Sort:** - **Bitonic Sequence**: a sequence that monotonically increases then decreases (or vice versa) — the key insight is that a bitonic sequence can be sorted in O(log n) parallel compare-and-swap steps - **Network Structure**: for n elements, the bitonic sorting network has log²(n)/2 stages, each containing n/2 independent compare-and-swap operations — all comparisons within a stage execute in parallel - **GPU Suitability**: the fixed comparison pattern requires no data-dependent branching — every thread performs the same operation on different data, making it ideal for SIMD/GPU execution with zero divergence - **Complexity**: O(n log²(n)) total work with O(log²(n)) parallel depth — not work-optimal (sequential is O(n log n)) but excellent parallel efficiency for GPU implementations up to millions of elements **Parallel Merge Sort:** - **Recursive Decomposition**: divide the array into P segments, sort each segment sequentially, then merge segments in a binary tree pattern — log(P) merge rounds with increasing parallelism within each merge - **Parallel Merge**: the merge of two sorted sequences can itself be parallelized — use binary search to find the rank of the median element, split into independent sub-merges, achieving O(n/P + log n) time per merge - **GPU Implementation**: CUB and Thrust libraries implement merge sort with block-level sorting (shared memory) followed by global merge passes — achieves 2-4 GB/s throughput for 32-bit keys on modern GPUs - **Cache Efficiency**: merge sort's sequential access pattern is cache-friendly — parallel merge sort maintains this advantage with each processor operating on contiguous memory regions **Parallel Radix Sort:** - **Non-Comparison Sort**: processes keys digit by digit (typically 4-8 bits at a time), using counting sort for each digit position — O(n × d/b) total work where d is key width and b is radix bits - **Parallel Counting**: each processor counts digit frequencies in its local partition, then a parallel prefix sum computes global offsets — the prefix sum is the key synchronization step - **GPU Radix Sort**: the fastest GPU sorting algorithm for uniform key distributions — processes 4 bits per pass with 8 passes for 32-bit keys, achieving 10+ GB/s on modern GPUs - **Stability**: radix sort is naturally stable (preserves order of equal keys) — critical for multi-key sorting (sort by secondary key first, then primary key) **Sample Sort (Distributed):** - **Splitter Selection**: each processor takes a random sample of its local data, the samples are gathered and sorted to select P-1 splitters that divide the key space into P roughly equal buckets - **Data Exchange**: each processor partitions its local data according to the splitters and sends each bucket to the corresponding processor — all-to-all communication pattern - **Local Sort**: after redistribution, each processor sorts its received bucket locally — the concatenation of sorted buckets produces the globally sorted result - **Load Balance**: oversampling (taking s×P samples per processor) ensures bucket sizes are within a factor of (1 + 1/s) of the ideal — s=4-16 provides excellent balance for most distributions **Sorting Networks for Small Arrays:** - **Odd-Even Merge Network**: O(n log²(n)) comparators with O(log²(n)) depth — used for small fixed-size sorts within GPU thread blocks - **Optimal Networks**: for n ≤ 16, minimal-depth sorting networks are known — hardcoded networks avoiding overhead of general-purpose sort algorithms - **Warp-Level Sort**: 32 elements sorted within a single GPU warp using shuffle instructions — no shared memory needed, achieves single-cycle comparisons via __shfl_xor_sync **Performance Comparisons (32-bit keys, modern GPU):** - **Radix Sort**: 10-15 GB/s for uniform distributions, fastest overall but performance degrades for highly skewed distributions - **Merge Sort**: 3-5 GB/s, consistent performance regardless of input distribution — preferred when stability and predictability matter - **Bitonic Sort**: 2-4 GB/s for power-of-two sizes, O(n log²(n)) extra work limits efficiency for very large arrays but simple implementation makes it popular for moderate sizes - **Thrust::sort**: NVIDIA's library automatically selects radix sort for primitive types and merge sort for custom comparators — 8-12 GB/s for common cases **Parallel sorting remains one of the most studied problems in parallel computing — the gap between theoretical optimal O(n log n / P) time and practical implementations continues to narrow as hardware evolves, with modern GPU sort implementations achieving within 2× of peak memory bandwidth throughput.**