Parallel Sorting Algorithms are the fundamental computational primitives that order N elements in O(N log N / P) time on P processors — where GPU-optimized sorts (radix sort, merge sort, bitonic sort) achieve throughputs of billions of keys per second by exploiting massive parallelism, coalesced memory access, and shared-memory-based local sorting to provide the ordered data that indexing, searching, database queries, and computational geometry require.

GPU Radix Sort — The Throughput Champion

Radix sort processes one digit (k bits) at a time from least significant to most significant: 1. Local Histogram: Each thread block computes a histogram of k-bit digit values for its tile of data. k=4 bits → 16 buckets. 2. Prefix Sum (Scan): Global scan of histograms computes output offsets for each digit bucket across all blocks. 3. Scatter: Each element is written to its computed output position based on its digit value and the prefix sum offset. 4. Repeat: For 32-bit keys with 4-bit digits: 8 passes. Each pass is O(N) — total is O(N × 32/k).

GPU radix sort achieves 5-10 billion 32-bit keys/second on modern GPUs (H100). CUB and Thrust provide highly optimized implementations.

Merge Sort — The Comparison-Based Champion

For arbitrary comparison functions (not just integers): 1. Block-Level Sort: Each thread block sorts its tile (1024-4096 elements) using sorting networks or insertion sort in shared memory. 2. Multi-Way Merge: Progressively merge sorted tiles into larger sorted sequences. GPU-optimized merge uses binary search to partition the merge task equally across threads — each thread determines which elements from the two input sequences belong to its output range. 3. Complexity: O(N log²N / P) for simple parallel merge; O(N log N / P) with optimal merge partitioning.

Bitonic Sort — The Network Sort

A comparison-based sorting network with fixed comparison pattern:

• Structure: Recursively builds bitonic sequences (first ascending, then descending), then merges them. log²N stages of parallel compare-and-swap operations.
• GPU Advantage: Fixed control flow — no data-dependent branches, perfect for SIMT execution. Every thread performs the same comparison pattern.
• Limitation: O(N log²N) work — not work-efficient. Best for small arrays (≤1M elements) or as a building block within merge sort for the final stages.

Performance Comparison

Sorting as a Primitive

GPU sorts are building blocks for higher-level operations:

• Database query processing: ORDER BY, GROUP BY, JOIN (sort-merge join).
• Computational geometry: Spatial sorting for kd-tree construction, z-order curve computation.
• Rendering: Depth sorting for transparency, tile binning for rasterization.
• Stream compaction: Sort by predicate key, then take the prefix.

Parallel Sorting Algorithms are the throughput engines that transform unordered data into searchable, joinable, and analyzable form — the computational primitives whose GPU implementations process billions of records per second, enabling real-time analytics on datasets that sequential sorting would take minutes to process.