#coding: utf-8
'''
O(dn)
d: digit size
n: element size
'''

from collections import defaultdict
from random import randint

def counting_general(A, key=lambda x: x):
    B, C = [], defaultdict(list)
    for x in A:
        C[key(x)].append(x)
    for k in range(min(C), max(C)+1):
        B.extend(C[k])
    return B


key_maker = lambda n: (lambda x: (0 if len(str(x)) < n else int(str(x)[-n])))

def radix_sort(target, digits):
    for d in range(1, digits+1):
        target = counting_general(target, key_maker(d))
    return target


if __name__ == "__main__":
    sp = [randint(0,1000) for x in range(10)]
    print "before:\n", sp
    print "after:\n", radix_sort(sp, 5)
