Radix Sort

radix_sort.py

def sort_counting(lst, exp):
    length = len(lst)

	
    # data ranges from 0 to 9
    occ = [0 for i in range(10)]

    # occurrence of each element
    for el in lst:
        index = el // exp
        occ[index % 10] += 1
 
    # cumulative
    for i, el in enumerate(occ):
        if i != 0:
            occ[i] = el + occ[i-1]

    res = [0 for i in range(length)]

    i = length - 1
    while i >= 0:
        index = lst[i] // exp
        res[occ[index % 10] - 1] = lst[i]
        occ[index % 10] -= 1
        i -= 1

	# copy array
    for i in range(0, length):
        lst[i] = res[i]
 
def sort_radix(lst): 
    highest = max(lst)

    exp = 1
    while highest // exp > 0:
        sort_counting(lst, exp)
        exp *= 10

lst = [170, 45, 75, 90, 802, 24, 2, 66]

sort_radix(lst)
print(lst)