An implementation of the counting-sort algorithm, including time complexity stats showing O(n)

counting_sort.py

"""A python example which shows the time complexity of the counting sort algorithm (O(n + k)).

The final output is a table showing the execution time of the counting sort algorithm for lists of different lengths.
Copied from my execution on my machine:

524288       (2**19) -> 0.25
1048576      (2**20) -> 0.49
2097152      (2**21) -> 0.92
4194304      (2**22) -> 1.75
8388608      (2**23) -> 3.47
16777216     (2**24) -> 6.91
33554432     (2**25) -> 14.33
67108864     (2**26) -> 27.14
134217728    (2**27) -> 69.56

And as can be seen, the execution time is linear with respect to the length of the list.
"""
import random
import time
from typing import List


def log_time(func):
    """A decorator that logs the time taken by a function to execute and returns it in addition to the result."""

    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        return result, round(time.time() - start_time, 2)

    return wrapper


@log_time
def counting_sort(numbers: List[int]) -> List[int]:
    """An implementation of the counting sort algorithm.

    Base assumption is that all numbers are non-negative integers.
    Based on https://www.youtube.com/watch?v=7zuGmKfUt7s&t=24s&pp=ygUNY291bnRpbmcgc29ydA%3D%3D
    """
    appearance_count = [0] * (max(numbers) + 1)
    for num in numbers:
        appearance_count[num] += 1

    last_modified_count = 0
    for i in range(len(appearance_count)):
        if appearance_count[i] == 0:
            continue
        appearance_count[i] = last_modified_count = last_modified_count + appearance_count[i]

    sorted_list = [None] * len(numbers)
    for num in numbers:
        sorted_list[appearance_count[num] - 1] = num
        appearance_count[num] -= 1

    return sorted_list


def main():
    print("List Length  -> Execution Time")

    for i in range(18, 28):
        random_list_len = 2 ** i
        random_list = [random.randint(0, 1_000_000) for _ in range(random_list_len)]

        result, execution_time = counting_sort(random_list)
        assert result == sorted(random_list)
        print(f"{str(random_list_len).ljust(12)} (2**{i}) -> {execution_time}")


if __name__ == '__main__':
    main()