counting sort

def unstable_counting_sort(arr, size):
    max_key = max(arr)
    count_arr: List[int] = [0] * (max_key + 1)

    for key in arr:
        count_arr[key] += 1

    cur_index: int = 0
    for index, counter in enumerate(count_arr):
        for _ in range(counter):
            arr[cur_index] = index
            cur_index += 1

def stable_counting_sort(arr: List[int], size: int):
    max_key = max(arr)
    count_arr: List[int] = [0] * (max_key + 1)
    output: List[int] = [None] * size

    # 1) count each item appearance in original array
    # 2) map each item key to corresponding index in count_array
    for key in arr:
        count_arr[key] += 1

    # for adding n item in a row you should now either lb or end index to do so
    # the following loop will make the count array to show end index of each item
    # by doing this you know the position of start adding item in output array
    for i in range(0, max_key):
        count_arr[i + 1] += count_arr[i]

    # for each key in original array find end index to replace it with
    # start from there untill you can not find anymore of that key in original array
    # this will make sorting stable because you place object in list by order
    # ... you find it in original array, so the order is not changed
    for i in range(size - 1, -1, -1):
        key = arr[i]
        count_arr[key] -= 1
        output[count_arr[key]] = key
    
    # update given array
    for index, item in enumerate(output):
        arr[index] = item