#!/usr/bin/env python
 
def counting_sort(array, maxval):
    """in-place counting sort"""
    n = len(array)
    m = maxval + 1
    count = [0] * m               # init with zeros
    for a in array:
        count[a] += 1             # count occurences
    i = 0
    for a in range(m):            # emit
        for c in range(count[a]): # - emit 'count[a]' copies of 'a'
            array[i] = a
            i += 1
    return array
 
print counting_sort( [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1], 7 )
 

IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCgpkZWYgY291bnRpbmdfc29ydChhcnJheSwgbWF4dmFsKToKICAgICIiImluLXBsYWNlIGNvdW50aW5nIHNvcnQiIiIKICAgIG4gPSBsZW4oYXJyYXkpCiAgICBtID0gbWF4dmFsICsgMQogICAgY291bnQgPSBbMF0gKiBtICAgICAgICAgICAgICAgIyBpbml0IHdpdGggemVyb3MKICAgIGZvciBhIGluIGFycmF5OgogICAgICAgIGNvdW50W2FdICs9IDEgICAgICAgICAgICAgIyBjb3VudCBvY2N1cmVuY2VzCiAgICBpID0gMAogICAgZm9yIGEgaW4gcmFuZ2UobSk6ICAgICAgICAgICAgIyBlbWl0CiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoY291bnRbYV0pOiAjIC0gZW1pdCAnY291bnRbYV0nIGNvcGllcyBvZiAnYScKICAgICAgICAgICAgYXJyYXlbaV0gPSBhCiAgICAgICAgICAgIGkgKz0gMQogICAgcmV0dXJuIGFycmF5CgpwcmludCBjb3VudGluZ19zb3J0KCBbMSwgNCwgNywgMiwgMSwgMywgMiwgMSwgNCwgMiwgMywgMiwgMV0sIDcgKQo=