Counting Sort

Implementation

class CountingSort(Sort[int]):
    def sort(self, array: list[int]) -> list[int]:
        counts: dict[int, int] = {}
        min = max = 0
        for n in array:
            counts[n] = counts.get(n, 0) + 1
            if n < min:
                min = n
            if n > max:
                max = n
        ret: list[int] = []
        for k in range(min, max+1):
            if (v := counts.get(k)) is None:
                continue
            ret.extend([k] * v)
        return ret