Size:15

Overview & Concept

Pigeonhole Sort is a non-comparison integer sorting algorithm suitable when the range between the minimum and maximum element (range = max - min + 1) is approximately the same as the number of elements n. It sets up an array of "pigeonholes" for each possible value, populates the holes, and sweeps through them linearly.

How It Works

Range Discovery: Identifies the minimum and maximum elements to determine the total pigeonhole count range.

Hole Allocation: Allocates an array of lists/counts of size range, indexed by (val - min).

Distribution: Iterates over the input array, placing each element into its corresponding pigeonhole slot.

Linear Sweep: Traverses pigeonhole slots in order from 0 to range - 1, collecting elements back into the array.

Step-by-Step Execution

1. Find Min and MaxScan array to compute minimum and maximum values; range = max - min + 1.

2. Allocate PigeonholesCreate an array of empty lists indexed from 0 to range - 1.

3. Scatter ElementsFor each element val, append to pigeonhole at index val - min.

4. Gather Sorted ArrayIterate through pigeonholes in order and write elements back sequentially.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n + range)	O(n + range)	O(n + range)	O(range)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure pigeonholeSort(A):
  min = min(A), max = max(A)
  range = max - min + 1
  holes = array of range empty lists
  for x in A: holes[x - min].append(x)
  idx = 0
  for hole in holes: for x in hole: A[idx++] = x
  return A

Algorithmic Invariants

Hole Ordering Invariant: All elements in hole h are identical in value and strictly less than all elements in hole h + 1.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Linear time complexity O(n + range), extremely fast when range is small.
•Stable sorting behavior preserves duplicate item ordering.
•Conceptually straightforward non-comparison sorting mechanism.

Trade-offs & Limitations

•Memory consumption O(range) becomes catastrophic when range >> n (e.g. [1, 1000000]).
•Restricted to integer keys.

Real-World Applications

Sensor Range Binning

Sorting discrete ADC sensor readings with known bounded ranges (e.g., 8-bit values 0-255).

Exam Grade Ranking

Ranking student test scores bounded between 0 and 100.

Decision Guide: When to Use

Ideal Scenarios

✓When key range (max - min) is comparable to or smaller than array length n.

Consider Alternatives When

✕When range is significantly larger than n (use Quick Sort or Radix Sort).

Compare trade-offs and complexity across complementary tools in AlgoViz.

Counting Sort Bucket Sort Radix Sort