LSD radix sort in Python with speed- and doctest test.

radix_sort.py

"""Ported from https://www.java67.com/2018/03/how-to-implement-radix-sort-in-java.html
Sort an integer list in-place using least significant digit radix sort in Python.
Usage:
>>> x = [180, 50, 10, 30, 10, 29, 60, 0, 17, 24, 12]; radix_sort(x); x
[0, 10, 10, 12, 17, 24, 29, 30, 50, 60, 180]

Time Complexity of Solution:
	Best Case O(k*n); Average Case O(k*n); Worst Case O(k*n),
	where k is the length of the longest number and n is the
	size of the input array.

	Note: if k is greater than log(n) then an n*log(n) algorithm would be a
		better fit. In reality we can always change the radix to make k
		less than log(n).
"""

def radix_sort(source):
	RADIX = 10
	#buckets = tuple([] for i in range(RADIX))
	buckets = [[] for i in range(RADIX)]  # 3% faster than a tuple in Python 3.7.4 32-bit on Windows 10 Home.

	# sort
	maxLength = False
	tmp = -1; placement = 1
	while not maxLength:
		maxLength = True
		
		# split input between lists
		for i in source:
			tmp = i // placement
			buckets[tmp % RADIX].append(i)
			if maxLength and tmp > 0:
				maxLength = False
		
		# empty lists into input array
		a = 0
		for bucket in buckets:
			for i in bucket:
				source[a] = i
				a += 1
			bucket.clear()
		
		# move to next digit
		placement *= RADIX

def test_speed():
	import timeit
	code = "x = [180, 50, 10, 30, 10, 29, 60, 0, 17, 24, 12]; radix_sort(x); x"
	return min(timeit.repeat(code, setup="from radix_sort import radix_sort", number=10000, repeat=10))

if __name__ == "__main__":
	#print(test_speed()); exit()

	print("Radix sort in Python")
	source = [181, 51, 11, 33, 11, 39, 60, 2, 27, 24, 12]

	print("An Integer array before sorting")
	print(source)
	print("Sorting an int array using radix sort algorithm")

	radix_sort(source)
	print(source)