Pigeonhole Sort Program with Explanation and Code

2025-11-19 pigeonhole sort integer sorting simple sorting algorithms bucket sorting non-comparative sort python pigeonhole sort c pigeonhole sort javascript pigeonhole sort php pigeonhole sort csharp pigeonhole sort

Pigeonhole Sort is a simple, non-comparative sorting algorithm ideal for sorting integers within a small range. This page explains how it works and includes complete program examples in Python, C, JavaScript, PHP, and C#. Great for beginners learning distribution-based sorting.

Program Explanation

What is Pigeonhole Sort?

Pigeonhole Sort is a simple sorting algorithm that works best when the number of elements and the range of key values are approximately the same. It places each element into a "pigeonhole" (bucket) according to its value and then collects the values back in sorted order. It is similar to Counting Sort but uses direct value-based buckets.

Steps to Solve

  1. Find the minimum and maximum values in the array.
  2. Calculate the range and create pigeonholes (buckets) for each possible value.
  3. Initialize each pigeonhole with count zero.
  4. Place each array element into its corresponding pigeonhole by increasing its count.
  5. Traverse all pigeonholes from smallest to largest.
  6. Reconstruct the sorted array by repeating the element according to its count.
  7. The array becomes sorted in ascending order.

Key Points

  • Works efficiently when range of numbers is small.
  • Time complexity: O(n + range).
  • Uses extra memory for pigeonholes.
  • Not suitable for large ranges due to high memory usage.
  • Works only for integers.
  • Simple and stable sorting algorithm.

Program Code


def pigeonhole_sort(arr):
    mn = min(arr)
    mx = max(arr)
    size = mx - mn + 1

    holes = [0] * size

    for num in arr:
        holes[num - mn] += 1

    index = 0
    for i in range(size):
        while holes[i] > 0:
            arr[index] = i + mn
            index += 1
            holes[i] -= 1

arr = list(map(int, input("Enter numbers: ").split()))
pigeonhole_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void pigeonholeSort(int arr[], int n) {
    int min = arr[0], max = arr[0];

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

    int range = max - min + 1;
    int holes[range];

    for (int i = 0; i < range; i++)
        holes[i] = 0;

    for (int i = 0; i < n; i++)
        holes[arr[i] - min]++;

    int index = 0;
    for (int i = 0; i < range; i++) {
        while (holes[i]-- > 0)
            arr[index++] = i + min;
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    pigeonholeSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function pigeonholeSort(arr) {
  let min = Math.min(...arr);
  let max = Math.max(...arr);
  let size = max - min + 1;

  let holes = Array(size).fill(0);

  for (let num of arr) holes[num - min]++;

  let index = 0;
  for (let i = 0; i < size; i++) {
    while (holes[i] > 0) {
      arr[index++] = i + min;
      holes[i]--;
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
pigeonholeSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void PigeonholeSort(int[] arr) {
        int min = arr[0], max = arr[0];

        foreach (int x in arr) {
            if (x < min) min = x;
            if (x > max) max = x;
        }

        int size = max - min + 1;
        int[] holes = new int[size];

        foreach (int x in arr)
            holes[x - min]++;

        int index = 0;
        for (int i = 0; i < size; i++) {
            while (holes[i] > 0) {
                arr[index++] = i + min;
                holes[i]--;
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        PigeonholeSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function pigeonholeSort(&$arr) {
    $min = min($arr);
    $max = max($arr);
    $size = $max - $min + 1;

    $holes = array_fill(0, $size, 0);

    foreach ($arr as $num)
        $holes[$num - $min]++;

    $index = 0;
    for ($i = 0; $i < $size; $i++) {
        while ($holes[$i] > 0) {
            $arr[$index++] = $i + $min;
            $holes[$i]--;
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
pigeonholeSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1