Counting sort in Python I wrote the following function to implement counting sort:

def CountSort( Arr, Max ):
    counter, retVal = [0] * (Max + 1), []
    for _ in Arr:
        counter[_] += 1
    for i in xrange( Max + 1 ):
        retVal += [i] * counter[i]
    return retVal


NOTE

The function takes the array of integer/list of integer as its first argument, and the maximum value it stores as the second. The only restriction is that the data in array should be distributed for \$0 \le x \le Max\$.

I'm not happy with it since I have to maintain two lists in memory now, namely Arr and retVal. I could, obviously, use the following:

    # indentation preserved
    pos = 0
    for i in xrange( Max + 1 ):
        while counter[i] &gt; 0:
            Arr[pos] = i
            pos += 1
            counter[i] -= 1


but it won't be as pythonic as the first one. An alternate approach is to delete the input Arr, and recreate it:

    # indentation preserved
    del Arr
    Arr = []
    for i in xrange( Max + 1 ):
        Arr += [i] * counter[i]


but this is not dissimilar to the second approach.

I'm open to suggestions on improvement of the first (or any of the latter).
Well, you kind of have to have two arrays. You need your counts array and you need your output array. If you want to sort the input array in place, you can do that, that's just a completely different semantic for your algorithm. So you'll just need to figure that out up front: do you want to sort the input list (a la list.sort()) or do you want to return a new list that is sorted (a la sorted()). 

That said, here's some comments on your initial solution. To start with:

counter, retVal = [0] * (Max + 1), []


There is no reason to do such a thing. That is unnecessary terse and you're just making it hard to see what's going on. Furthermore, you don't even need retVal for now. So let's just start with the counter by itself:

counter = [0] * (Max + 1)
for _ in Arr:
    counter[_] += 1


Next, we have this loop:

for i in xrange( Max + 1 ):
    retVal += [i] * counter[i]


You can actually do a little better in terms of code appearance. We have our counter array, which has all of those indices... what we want to do is iterate over the counter array while also having access to the indices. That's what enumerate() is for:

retVal = []
for i, count in enumerate(counter):
    retVal += [i] * count
return retVal




Lastly, if you want to follow PEP-8, your function name should really be counting_sort(). And _ should probably be replaced with some single-letter name (x, a, elem, what have you).