Pigeonhole Sort

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();
}