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.