Parallel Merge Sort Algorithm
Parallel Sorting Algorithms are fundamental building blocks of parallel computing that exploit massive thread-level parallelism to sort arrays orders of magnitude faster than sequential comparison sorts — with GPU-optimized radix sort achieving billions of keys per second on modern hardware.
Sorting Network Approaches:
- Bitonic Sort: recursively constructs bitonic sequences (ascending then descending) and merges them with compare-and-swap networks; O(N log²N) work, O(log²N) depth; completely data-oblivious (every comparison is predetermined regardless of input values), making it ideal for GPU implementation
- Odd-Even Merge Sort: divides input recursively, sorts halves, then merges with an odd-even network; O(N log²N) work like bitonic sort but with different comparison patterns; good for FPGA implementations with fixed routing
- Batcher's Merge Network: general framework for constructing sorting networks of depth O(log²N); AKS network achieves optimal O(log N) depth but with impractically large constants — theoretical interest only
Radix Sort (GPU-Optimized):
- Algorithm: processes keys digit-by-digit from least significant to most significant; each pass is a stable partition by the current radix digit value; 32-bit keys with radix-256 require 4 passes
- GPU Implementation: each radix pass consists of: (1) compute per-block digit histograms, (2) exclusive prefix sum of histograms for scatter addresses, (3) scatter elements to sorted positions; achieves O(N × k/b) work for k-bit keys with radix 2^b
- Performance: CUB/Thrust radix sort achieves 10-15 billion 32-bit keys/second on A100 GPU — 50-100× faster than optimized CPU quicksort; dominates for large arrays of primitive types
- Key-Value Sort: simultaneously sorts key-value pairs by rearranging both arrays according to key order — essential for database operations, sparse matrix construction, and particle simulations
Merge-Based Parallel Sort:
- Parallel Merge Sort: divide array into chunks, sort chunks independently (possibly with different algorithms), merge sorted chunks pairwise in O(log P) rounds; merge step itself is parallelizable using co-rank-based partitioning
- Sample Sort: generalization of quicksort to P processors; select P-1 splitters from random sample, partition data into P buckets using splitters, sort each bucket independently; achieves near-perfect load balance with oversampling
- GPU Merge Path: binary search to find equal-work partition points in two sorted arrays, enabling perfectly load-balanced parallel merge; each thread or block processes exactly N/P elements
Comparison and Selection:
- Small Arrays (<100K): sorting networks (bitonic) or warp-level sort sufficient; minimal kernel launch overhead matters more than asymptotic complexity
- Medium Arrays (100K-100M): radix sort dominates for integer/float keys; merge sort competitive for complex comparison functions
- Distributed Sort: sample sort or histogram sort across nodes with MPI communication; communication volume O(N/P) per node in best case; network bandwidth limits scaling beyond ~1000 nodes
- Stability: radix sort and merge sort are stable (preserve relative order of equal keys); bitonic sort and quicksort are not
Parallel sorting is one of the most well-studied problems in parallel computing, with GPU radix sort representing the gold standard for throughput on primitive types — achieving sorting rates that exceed 10 billion keys per second and enabling real-time database query processing and scientific data analysis at scale.