this is an implementation of pigeon hole sort for doctests run following command python3 m doctest v pigeonsort py or python m doctest v pigeonsort py for manual testing run python pigeonsort py implementation of pigeon hole sort algorithm param array collection of comparable items return collection sorted in ascending order pigeonsort0 5 3 2 2 0 2 2 3 5 pigeonsort pigeonsort2 5 45 45 5 2 compute the variables make the sorting makes the array back by replacing the numbers returns the sorted array implementation of pigeon hole sort algorithm param array collection of comparable items return collection sorted in ascending order pigeon_sort 0 5 3 2 2 0 2 2 3 5 pigeon_sort pigeon_sort 2 5 45 45 5 2 compute the variables make the sorting makes the array back by replacing the numbers returns the sorted array
from __future__ import annotations


def pigeon_sort(array: list[int]) -> list[int]:
    
    if len(array) == 0:
        return array

    _min, _max = min(array), max(array)

    
    holes_range = _max - _min + 1
    holes, holes_repeat = [0] * holes_range, [0] * holes_range

    
    for i in array:
        index = i - _min
        holes[index] = i
        holes_repeat[index] += 1

    
    index = 0
    for i in range(holes_range):
        while holes_repeat[i] > 0:
            array[index] = holes[i]
            index += 1
            holes_repeat[i] -= 1

    
    return array


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    user_input = input("Enter numbers separated by comma:\n")
    unsorted = [int(x) for x in user_input.split(",")]
    print(pigeon_sort(unsorted))