Counting Sort

def counting_sort(arr):
    # find the max value
    max_val = max(arr)

    # initialize array, length is max value plus 1 (may require large memory here)
    count = [0] * (max_val + 1)

    # count the occurrences of each number
    for num in arr:
        count[num] += 1

    # get data back according to count array
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])

    return sorted_arr


arr = [4, 2, 2, 8, 3, 3, 1]
print("Original:", arr)
sorted_arr = counting_sort(arr)
print("After:", sorted_arr)
# Original: [4, 2, 2, 8, 3, 3, 1]
# After: [1, 2, 2, 3, 3, 4, 8]