Parallel Sorting Algorithms are the foundational parallel computing primitives that order N elements across P processors in O((N log N)/P + overhead) time — where the "overhead" (communication, synchronization, load balancing) distinguishes practical parallel sorts from theoretical ones, and the choice of algorithm depends on whether the target is shared-memory (GPU/multicore), distributed-memory (cluster), or a hybrid system.

Why Parallel Sorting Is Hard

Sorting is inherently comparison-based (Omega(N log N) lower bound) with data-dependent access patterns that resist simple parallelization. Unlike embarrassingly parallel workloads, sorting requires extensive data movement — elements must physically migrate to their correct sorted position, which may be on a different processor. The communication pattern depends on the data, making load balancing and locality optimization challenging.

Key Algorithms

• Bitonic Sort: A comparison network that sorts by recursively creating bitonic sequences (sequences that first increase then decrease) and merging them. The network has O(log²N) parallel comparison stages, each independently parallelizable. Fixed communication pattern (oblivious to data) makes it ideal for GPU implementation — no data-dependent branching. Complexity: O(N log²N / P) work with O(log²N) depth.

• Parallel Merge Sort: Each processor sorts its local partition (N/P elements) using sequential quicksort, then pairs of processors merge their sorted sequences in a tree pattern. O(log P) merge rounds, each requiring O(N/P) communication. The dominant algorithm for distributed-memory systems. Bottleneck: the final merge stage involves all N elements passing through a single pair.

• Sample Sort: A generalization of quicksort to P processors. Randomly sample s elements from each processor, gather all samples, sort them, and select P-1 splitters that divide the key range into P equal buckets. Each processor sends elements to the appropriate bucket owner. After redistribution, each processor sorts its bucket locally. Expected O(N log N / P) with O(N/P) communication. The preferred algorithm for large-scale distributed sorting.

• Radix Sort (Parallel): Non-comparison sort that processes one digit (or bit/byte) at a time using parallel prefix sum (scan) to compute destination positions. Each radix pass is an all-to-all redistribution. Complexity: O(d × N/P) where d is the number of digits. Optimal for integer and fixed-length key sorting on GPUs — NVIDIA CUB and AMD rocPRIM provide highly-optimized GPU radix sorts achieving billions of keys per second.

GPU-Specific Considerations

• Warp-Level Sorting: For small arrays (≤32 elements), sorting within a single warp using shuffle instructions avoids shared memory entirely — the fastest possible sort for small N.
• Block-Level Merge: Bitonic or odd-even merge networks within a thread block using shared memory. Thousands of elements sorted at shared memory bandwidth.
• Global Merge: Multi-block merge of sorted segments using global memory. NVIDIA Thrust and CUB implement highly-tuned merge paths that balance work across threads despite variable-length segments.

Parallel Sorting is the benchmark by which parallel systems prove their worth — because sorting's combination of computation, communication, and load-balancing challenges tests every aspect of a parallel architecture's design.