Sample Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Sample Sort

A parallel divide-and-conquer distribution sort: selects a small sample of elements to extract multiple splitters, partitioning the array into many buckets that can be sorted concurrently.

How it works

Sample Sort is a generalization of Quicksort designed for distributed-memory parallel systems. While Quicksort uses a single pivot to partition elements into 2 sub-problems, Sample Sort partitions elements into \(P\) sub-problems (where \(P\) is the number of processors) using \(P - 1\) pivots called "splitters":

1. Sampling: Select a small, representative sample of elements from the input array.
2. Splitter Selection: Sort the sample. Pick \(P - 1\) splitter values at uniform intervals in the sorted sample (e.g. if \(P = 3\), we extract 2 splitters). These splitters define the boundary ranges of \(P\) buckets.
3. Local Distribution: Distribute the remaining elements into the \(P\) buckets based on the splitters. On a parallel system, each processor performs this distribution locally.
4. Parallel Sort: Sort each bucket independently (often using a fast comparison sort like Insertion Sort or Quicksort). Because the buckets represent disjoint value ranges, they can be processed concurrently with zero inter-processor communication.
5. Recombination: Concatenate the sorted buckets back together to form the final sorted array.

Complexity

Interactive visualization

Pseudocode

procedure sampleSort(A, P):
  n ← length(A)
  sampleSize ← P * 5
  sample ← chooseRandomSamples(A, sampleSize)
  sort(sample)
  
  splitters ← array of size P - 1
  for i from 0 to P - 2:
    splitters[i] ← sample[(i + 1) * 5]
    
  buckets ← array of P empty lists
  for each x in A:
    bucketIdx ← findBucket(x, splitters)
    buckets[bucketIdx].append(x)
    
  A ← empty
  for each bucket in buckets:
    sort(bucket)
    A.appendAll(bucket)

JavaScript implementation

function sampleSort(arr, P = 3) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  // 1. Select sample indices
  const sampleIdxs = [arr[0], arr[Math.floor(n/4)], arr[Math.floor(n/2)], arr[Math.floor(n*3/4)], arr[n - 1]];
  sampleIdxs.sort((x, y) => x - y);
  
  // 2. Pick splitters
  const s1 = sampleIdxs[1];
  const s2 = sampleIdxs[3];
  
  // 3. Distribute into buckets
  const buckets = Array.from({ length: P }, () => []);
  for (let x of arr) {
    if (x < s1) {
      buckets[0].push(x);
    } else if (x < s2) {
      buckets[1].push(x);
    } else; {
      buckets[2].push(x);
    }
  }
  
  // 4. Sort buckets and combine
  let current = 0;
  for (let b = 0; b < P; b++) {
    buckets[b].sort((x, y) => x - y);
    for (let x of buckets[b]) {
      arr[current++] = x;
    }
  }
  return arr;
}

Pros and cons

When (not) to use it

• Distributed computing networks: Standard choice for parallel database processing, MPI clusters, and map-reduce frameworks.
• Single-threaded systems: Avoid; Quicksort or Timsort have lower constant factors on single-core platforms.