#! /usr/bin/env python
# DataStructure Sort


# InsertSort
def InsertSort(lst, end=None, beg=0, space=1):
    if end is None:
        end = len(lst)
    for i in range(beg, end, space):
        tmp = lst[i]
        j = i-space
        while j>=beg and tmp < lst[j]:
            lst[j+space] = lst[j]
            j -= space
        lst[j+space] = tmp


# ShellSort
def ShellSort(lst):
    spaces = [5,3,1]
    # 5->3->1
    for space in spaces:
        for i in range(space):
            InsertSort(lst, len(lst), i, space)
        # print lst


# BubbleSort
def BubbleSort(lst):
    for i in range(len(lst)-1, 0, -1):
        flag = 0
        for j in range(1, i+1):
            if lst[j-1] > lst[j]:
                tmp = lst[j-1]
                lst[j-1] = lst[j]
                lst[j] = tmp
                flag = 1
        if flag == 0:
            return


# QuickSort
def QuickSort(lst, l, r):
    i=l
    j=r
    if l<r:
        tmp = lst[l]
        while i!=j :
            while j>i and lst[j]>tmp:
                j -= 1
            if i<j:
                lst[i] = lst[j]
                i += 1

            while i<j and lst[i]<tmp:
                i += 1
            if i<j:
                lst[j] = lst[i]
                j -= 1
        lst[i] = tmp
        QuickSort(lst, l, i-1)
        QuickSort(lst, i+1, r)

def QSort(lst):
    QuickSort(lst, 0, len(lst)-1)


# SelectSort
def SelectSort(lst):
    for i in range(len(lst)):
        k = i
        for j in range(i+1, len(lst)):
            if lst[j] < lst[k]:
                k = j
        tmp = lst[k]
        lst[k] = lst[i]
        lst[i] = tmp


# MergeSort
def MergeSort(lst):
    i = 2
    length = len(lst)
    while i<length:
        tmp = length
        j = 0
        while tmp:
            n = i
            if tmp < i:
                n = tmp
                tmp = 0
            else:                
                tmp -= n
            # Pay attention to j+n, j+n is end.
            InsertSort(lst, j+n, j)
            j += i
        i = i << 1
        # print lst
    InsertSort(lst, length)


# BaseSort
def BaseSort(lst):
    maxnum = max(lst)
    mod = 1
    barrel = [[] for i in range(10)]    # [[]] * 10 not work
    while mod <= maxnum:
        mod *= 10
        length = len(lst)
        for i in range(length):
            index = lst[0] % mod
            index = index*10 // mod
            barrel[index].append(lst.pop(0))
        for i in range(10):
            length = len(barrel[i])
            for j in range(length):
                lst.append(barrel[i].pop(0))    
        # print lst


if __name__ == "__main__":
    nums = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
    # InsertSort(nums)
    # BubbleSort(nums)
    # QSort(nums)
    # SelectSort(nums)
    # ShellSort(nums)
    # MergeSort(nums)
    BaseSort(nums)
    print nums