ProxmapSort: Mechanism, Complexity Analysis & Interactive Visualizer

ProxmapSort

A high-performance distribution sort: maps elements directly to their proximity slots in a destination array using a mapping function, resolving slot collisions with local insertion sort.

How it works

ProxmapSort (Proximity Map Sort), designed by Thomas A. Standish in 1997, is a variation of bucket sort that avoids the space overhead of creating multiple linked-list buckets. Instead, it pre-calculates the exact start positions of each bucket in a single destination array:

1. Key Mapping Function: Establish a mapping function that scales the key values to array indices from \(0\) to \(n - 1\).
2. Map & Counts Calculation: Read the keys once to count how many elements map to each index slot. Accumulate these counts to build a *Proximity Map* containing the starting index of each bucket in the sorted array.
3. Distribution & Local Sort: Iterate through the original array. For each element, map it to its designated starting position in the destination array. If the slot is empty, write it directly. If it is already occupied (a collision), perform a local Insertion Sort within the bucket by shifting items to the right.

Complexity

Interactive visualization

Pseudocode

procedure proxmapSort(A):
  n ← length(A)
  minVal, maxVal ← findMinMax(A)
  
  count ← array of size n filled with 0
  for each x in A:
    count[mapKey(x, minVal, maxVal, n)] ← count[mapKey(x)] + 1
    
  mapStart ← array of size n
  cumulative ← 0
  for i from 0 to n - 1:
    mapStart[i] ← cumulative
    cumulative ← cumulative + count[i]
    
  dest ← array of size n filled with empty
  nextSlot ← copy of mapStart
  
  for each x in A:
    key ← mapKey(x, minVal, maxVal, n)
    insertIdx ← nextSlot[key]
    
    k ← insertIdx
    while k > mapStart[key] and dest[k - 1] > x:
      dest[k] ← dest[k - 1]
      k ← k - 1
    dest[k] ← x
    nextSlot[key] ← nextSlot[key] + 1
    
  copy dest back to A

JavaScript implementation

function proxmapSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;
  
  let min = arr[0], max = arr[0];
  for (let x of arr) {
    if (x < min) min = x;
    if (x > max) max = x;
  }
  const range = max - min;
  if (range === 0) return arr;
  
  const mapKey = (val) => Math.min(n - 1, Math.floor(((val - min) / range) * (n - 1)));
  const count = new Array(n).fill(0);
  for (let x of arr) count[mapKey(x)]++;
  
  const mapStart = new Array(n).fill(0);
  let cumulative = 0;
  for (let i = 0; i < n; i++) {
    mapStart[i] = cumulative;
    cumulative += count[i];
  }
  
  const dest = new Array(n).fill(null);
  const nextSlot = [...mapStart];
  
  for (let x of arr) {
    const key = mapKey(x);
    let k = nextSlot[key];
    while (k > mapStart[key] && dest[k - 1] > x) {
      dest[k] = dest[k - 1];
      k--;
    }
    dest[k] = x;
    nextSlot[key]++;
  }
  
  for (let i = 0; i < n; i++) arr[i] = dest[i];
  return arr;
}

Pros and cons

When (not) to use it

• Uniform key distribution: Excellent for sorting large sets of floating-point values or uniformly distributed integers.
• Adversarial key clusters: Avoid when keys can clump densely (e.g. duplicating values), as the local sorting overhead degrades it to \(O(n²)\).