Parallel Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Parallel Merge Sort

A concurrent divide-and-conquer algorithm: breaks the input down recursively, sorts sub-partitions concurrently on separate threads, and merges sorted fragments in parallel stages.

How it works

Merge Sort is a natural fit for parallelization due to its divide-and-conquer structure. In a sequential merge sort, sub-calls run one after another. In Parallel Merge Sort, recursive branches run concurrently on separate processors or threads:

1. Recursive Thread Spawn: Divide the array into left and right halves. Instead of sorting them sequentially, spawn a new thread (or push a task to a thread pool) to sort the right half, while the current thread sorts the left half.
2. Leaf Execution: As long as the sub-array sizes are above a threshold (the "grain size"), threads continue to spawn recursively. Below this threshold, execution switches to standard sequential Merge Sort or Insertion Sort to avoid thread creation overhead.
3. Synchronization (Join): Wait for both concurrent child threads to finish sorting.
4. Merge: Merge the two sorted halves back into a single sorted range. The merge phase itself can also be parallelized (using binary search partitions) to achieve even faster sorting speeds.

Complexity

Interactive visualization

Pseudocode

procedure parallelMergeSort(A, left, right):
  if right - left < threshold:
    sequentialMergeSort(A, left, right)
  else:
    mid ← (left + right) / 2
    
    spawn parallelMergeSort(A, left, mid)
    parallelMergeSort(A, mid + 1, right)
    
    sync  # Wait for spawned branch to finish
    parallelMerge(A, left, mid, right)

JavaScript implementation

// Demonstrating parallel merge sorting using modern Web Workers API
async function parallelMergeSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  // Threshold size to switch to single-threaded sorting
  const threshold = 1024;
  if (n < threshold) {
    return arr.sort((x, y) => x - y);
  }
  
  const mid = Math.floor(n / 2);
  const leftHalf = arr.slice(0, mid);
  const rightHalf = arr.slice(mid);
  
  // Run left and right halves in parallel Web Workers
  const [sortedLeft, sortedRight] = await Promise.all([
    spawnWorkerSort(leftHalf),
    spawnWorkerSort(rightHalf)
  ]);
  
  // Merge results
  return merge(sortedLeft, sortedRight);
}

Pros and cons

When (not) to use it

• Multi-threaded systems: Standard choice in Java's ForkJoinPool (`Arrays.parallelSort`), C++ Parallel STL, and Rust's Rayon library.
• Resource-constrained systems: Avoid in memory-constrained setups (like microcontrollers) where the O(n) space allocation is unacceptable.