Counting Sort

def counting(lst):
    #For some reason hash(-1) = -2, the rest makes sence.
    if lst:
        smallest = lst[0].__hash__()
        largest = lst[0].__hash__()
    else:
        smallest = 0
        largest = 0
    for x in lst:
        x = x.__hash__()
        if x > largest:
            largest = x
        if x < smallest:
            smallest = x
    mapping = []
    for x in range(smallest, largest + 1):
        mapping.append(0)
    for x in lst:
        x = x.__hash__()
        mapping[x - smallest] += 1
    print smallest
    print mapping
    for x in range(len(mapping) - 1):
        mapping[x + 1] += mapping[x]
    oldlist = lst[:]
    for x in oldlist:
        lst[mapping[x.__hash__() - smallest] - 1] = x
        mapping[x.__hash__() - smallest] -= 1
Advertisements