Pigeonhole Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Pigeonhole Sort

A simple, non-comparison sorting algorithm that is ideal when the range of values is approximately equal to the number of elements.

How it works

Pigeonhole Sort is closely related to Counting Sort, but instead of maintaining a count array and accumulating prefix sums, it maps elements directly into a set of "pigeonholes" (lists) corresponding to each possible value in the range, and then copies them back.

1. Find the minimum and maximum values in the input array.
2. Calculate the range: range = max - min + 1.
3. Set up an array of empty "pigeonholes" (lists) of size equal to the range.
4. Scan the input array and append each element x to the list at index x - min.
5. Iterate through the pigeonholes in order and write the elements back to the original array.

Complexity

Interactive visualization

Pseudocode

procedure pigeonholeSort(A):
  n ← length(A)
  min, max ← findMinMax(A)
  range ← max - min + 1
  holes ← array of range empty lists
  
  for i from 0 to n - 1:
    holes[A[i] - min].append(A[i])
    
  idx ← 0
  for i from 0 to range - 1:
    for j from 0 to length(holes[i]) - 1:
      A[idx] ← holes[i][j]
      idx ← idx + 1

JavaScript implementation

function pigeonholeSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }

  const range = max - min + 1;
  const holes = Array.from({ length: range }, () => []);

  for (let i = 0; i < n; i++) {
    holes[arr[i] - min].push(arr[i]);
  }

  let idx = 0;
  for (let i = 0; i < range; i++) {
    for (let j = 0; j < holes[i].length; j++) {
      arr[idx++] = holes[i][j];
    }
  }
  return arr;
}

Pros and cons

When to use it

• Tight Integer Distribution: when sorting integer datasets where range $N$ matches size $n$.
• Simple Objects: ideal when keys are dense and stability is required.