AlgoViz: Interactive Algorithm Visualization Tool

Pigeonhole Sort

Category: Sorting | Time: O(n + N) | Space: O(N)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Pigeonhole Sort

A sorting algorithm that is suitable for sorting lists of elements where the number of elements and the number of possible key values are approximately the same. It requires knowing the range of the values in advance.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function pigeonholeSort(arr) {
    let min = Math.min(...arr);
    let max = Math.max(...arr);
    let range = max - min + 1;
    let holes = new Array(range).fill(0).map(() => []);

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

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

What is Pigeonhole Sort?

How does Pigeonhole Sort work?

What is its time complexity?

What is the main limitation of Pigeonhole Sort?

How is it related to Counting Sort?

What is the space complexity?

Is Pigeonhole Sort a stable algorithm?

Can Pigeonhole Sort be used for floating-point numbers?

Is this an in-place sorting algorithm?

Why isn't Pigeonhole Sort used more commonly?

Where can I learn more?