Pigeonhole Sort

#javascript #programming #algorithms

What do we understand about Pigeonhole Sort?

Very very very simple and straightforward sorting algorithm
One of the most effecient sorting algorithm with JS implementation to be as fast as 1 digit millisecond
Is NOT a comparison sort
ONLY Interger values from negative to positive
Stable algorithm
Handles sorting by placing integer value by index of new Array
The new Array's index holds an Array of the copied integer value when interated over
In JS can be done in ONE loop
Returns a new Array
Time complexity
- Best is O(n+k)
- Average is O(n+k)
- Worst is O(n+k)
Space complexity
- O(n+k)
Note: n – Size of array, k - Range of value

function PigeonHoleSort(arr) {
  const min = Math.min(...arr);
  const pigeonhole = [];

  arr.forEach(num => {
    if (pigeonhole[num - min]) pigeonhole[num - min].push(num);
    else pigeonhole[num - min] = [num];
  });
  return pigeonhole.flat();
}