Counting Sort implementation.

counting_sort.py

"""
Counting sort implementation.

This module implements the counting_sort function.

>>> counting_sort([1, 4, 1, 2, 7, 5, 2])
[1, 1, 2, 2, 4, 5, 7]
"""

def counting_sort(l: list) -> list:
    """Return the sorted version of l.

    >>> counting_sort([102, 85, 94])
    [85, 94, 102]
    """
    # create an aux list with length of max(l)+1
    aux = [0] * (max(l)+1)    
    # store the number of repetitions of l's elements in aux
    for i in l:
        aux[i] += 1
    # sum each aux's element with its predecessor
    for i in range(1, len(aux)):
        aux[i] += aux[i-1]
    # fill res with l's elements in the correct positions
    res = [None] * len(l)
    for i in l:
        res[aux[i]-1] = i
        aux[i] -=1
    return res