How can I implement a CountingSort that works with negative numbers?

Question

I have the following implementation of a Counting Sort algorithm in Python, but it doesn't work with arrays that contains negative numbers. Could someone help me?

def counting(nlist):
    nlist = list(nlist)
    size = len(nlist)

    if size < 2:
        return nlist

    k = max(nlist)

    counter = [0] * ( k + 1 )

    for i in nlist:
        counter[i] += 1

    ndx = 0;
    for i in range( len( counter ) ):
        while 0 < counter[i]:
           nlist[ndx] = i
           ndx += 1
           counter[i] -= 1

   return nlist

Answer 1

A simple approach would be just to find the minimum value and offset your indices by that amount, so that the minimum value is stored in array index 0 of counter. Then in your while loop, add the minimum value back on to get the original values:

m = min(nlist)
k = max(nlist) - m

counter = [0] * ( k + 1 )

for i in nlist:
    counter[i-m] += 1

ndx = 0;
for i in range( len( counter ) ):
    while 0 < counter[i]:
       nlist[ndx] = i+m
       ndx += 1
       counter[i] -= 1

Answer 2

You could look up the lowest value in your input, and add that to your index all the way, converting it back when your build the output:

def counting(nlist):
    nlist = list(nlist)
    size = len(nlist)

    if size < 2:
        return nlist

    low = min(nlist)
    k = max(nlist) - low

    counter = [0] * ( k + 1 )

    for i in nlist:
        counter[i - low] += 1

    print(counter) # see what the counter list looks like. Remove in final version 
    ndx = 0;
    for i in range( len( counter ) ):
        while 0 < counter[i]:
            nlist[ndx] = i + low
            ndx += 1
            counter[i] -= 1

    return nlist