O(kn) integer sorting

radix_sort.py

def max_num_len(arr):
    x = max(arr)
    count = 0
    while x > 0:
        x /= 10
        count += 1
    return count


def radix_sort(arr):
    for i in range(max_num_len(arr) + 1):
        bins = [[] for _ in range(10)]
        for elem in arr:
            bins[(elem / (10 ** i)) % 10].append(elem)
        arr = []
        for section in bins:
            arr.extend(section)
    return arr

if __name__ == '__main__':
    from random import shuffle
    z = range(25)
    shuffle(z)
    print z
    print radix_sort(z)