radix_sort.py

from typing import List


def get_digit(i: int, d: int, b: int) -> (int, bool):
	di = i // (b ** d)
	return int(di % b), di // b == 0


def counting_sort(a: List[int], k: int, d: int, s: int) -> (List[int], int):
	b = [0] * len(a)
	c = [0] * (k * 2)

	for j in range(0, len(a)):
		digit, is_last = get_digit(a[j], d, k)
		c[k * (not is_last) + digit] += 1

	for i in range(1, k * 2):
		c[i] += c[i - 1]

	for j in range(len(a) - 1, -1, -1):
		digit, is_last = get_digit(a[j], d, k)
		if is_last:
			s += 1
		c[k * (not is_last) + digit] -= 1
		b[c[k * (not is_last) + digit]] = a[j]

	return b, s


def radix_sort(a: List[int], k: int) -> List[int]:
	result = a[0:len(a)]
	done = 0
	digit = 0

	while done != len(a):
		result[done:len(a)], done = counting_sort(result[done:len(a)], k, digit, done)
		digit += 1
	return result


r = radix_sort([10000, 44, 9, 99, 55, 131, 39, 2, 0], 10)
print(r)

Modified Radix-sort written in Python, that takes into account only significant part of positive numbers and ignores leading zeros