Parallel Radix Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Parallel Radix Sort

A non-comparison parallel sorting algorithm: counts digit frequencies concurrently across local thread processors, computing prefix sums to place items stably in parallel memory offsets.

How it works

Parallel Radix Sort parallelizes Radix Sort (typically Least Significant Digit - LSD) across multiple threads. Instead of having a single CPU count and write digit buckets, the load is divided into coordinate processors:

1. Processor Sub-Partitioning: Divide the array into \(P\) equal blocks (e.g. 2 blocks for 2 simulated processors). Each processor receives a dedicated partition.
2. Parallel Local Counting: For each digit place (ones, tens, hundreds...):
   • Each processor scans its local block and populates its own **local count array** indicating how many times each digit appears.
3. Global Prefix Scan (Reduction): Perform a parallel prefix sum across the count tables of all processors. This prefix sum establishes the exact starting index offset where each processor must write elements for each digit bucket.
4. Parallel Memory Writes: Each processor reads its partition, maps each value to its digit, and writes it directly to its computed offset in a temporary output array. The offset is then incremented. Because offsets are disjoint, threads can write concurrently with no race conditions.
5. Next Digit Pass: Copy the temporary array back and repeat the cycle for the next digit.

Complexity

Interactive visualization

Pseudocode

procedure parallelRadixSort(A, P):
  maxVal ← findMax(A)
  
  for exp ← 1 to maxVal step exp * radix:
    # Step 1: Thread-local counts in parallel
    localCounts ← array of size P × radix filled with 0
    parallel for pid ← 0 to P - 1:
      start, end ← getPartitionBounds(pid, length(A))
      localCounts[pid] ← countDigits(A, start, end, exp)
      
    # Step 2: Global prefix sum (scan)
    offsets ← computeGlobalOffsets(localCounts, P)
    
    # Step 3: Parallel distribution write
    temp ← array of size length(A)
    parallel for pid ← 0 to P - 1:
      start, end ← getPartitionBounds(pid, length(A))
      for i from start to end:
        digit ← (A[i] / exp) % radix
        destIdx ← offsets[pid][digit]
        temp[destIdx] ← A[i]
        offsets[pid][digit] ← destIdx + 1
        
    copy temp back to A

JavaScript implementation

// Simulating Parallel Radix Sort logic using 2 partition threads
function parallelRadixSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  const maxVal = Math.max(...arr);
  const P = 2; // 2 simulated processors
  const mid = Math.floor(n / P);
  
  for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) {
    const count0 = new Array(10).fill(0);
    const count1 = new Array(10).fill(0);
    
    // Processor 0 local count
    for (let i = 0; i < mid; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      count0[digit]++;
    }
    
    // Processor 1 local count
    for (let i = mid; i < n; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      count1[digit]++;
    }
    
    // Global Prefix Sum computation
    const pref = new Array(10).fill(0);
    let cumulative = 0;
    for (let d = 0; d < 10; d++) {
      pref[d] = cumulative;
      cumulative += count0[d] + count1[d];
    }
    
    // Distribute offsets
    const offset0 = [...pref];
    const offset1 = [];
    for (let d = 0; d < 10; d++) {
      offset1.push(pref[d] + count0[d]);
    }
    
    const temp = new Array(n).fill(0);
    
    // Processor 0 writes
    for (let i = 0; i < mid; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      temp[offset0[digit]++] = arr[i];
    }
    
    // Processor 1 writes
    for (let i = mid; i < n; i++) {
      const digit = Math.floor(arr[i] / exp) % 10;
      temp[offset1[digit]++] = arr[i];
    }
    
    for (let i = 0; i < n; i++) arr[i] = temp[i];
  }
  return arr;
}

Pros and cons

When (not) to use it

• GPU Compute Engines: Broadly used on GPU sorting pipelines (like Thrust in CUDA) where thousands of parallel threads execute prefix scans concurrently.
• Standard CPUs: Avoid on sequential architectures; the extra synchronization steps degrade performance compared to standard Timsort or Quicksort.