Mental Model:

- Get
**range**of collection - Create
array (of length equal to range)`counts`

**Count occurrences**of each element`i`

and store in`counts[i]`

**Sum each position**of the element with predecessors.- Create an
array`output`

- Populate the
**output**such that:

Now,

`counts[i]`

shows
`# of elements <= i`

in the collection`output[ of the position of collection[i] in the counts array (which is sorted) ] = collection[i]`

```
def counting_sort(collection):
# if the collection is empty, returns emptyif collection == []:
return []
# get some information about the collection
collection_length = len(collection)
collection_max = max(collection)
collection_min = min(collection)
# create the counting array
counts_len = collection_max + 1 - collection_min
counts = [0] * counts_len
# count how much a number appears in the collectionfor number in collection:
counts[number - collection_min] += 1
# sum each position with it's predecessors. now, counts[i] tells
# us how many elements <= i has in the collection
for i in range(1, counts_len):
counts[i] = counts[i] + counts[i - 1]
# create the output collection
ordered = [0] * collection_length
# place the elements in the output, respecting the original order (stable
# sort) from end to begin, updating counts
for i in reversed(range(0, collection_length)):
ordered[counts[collection[i] - collection_min] - 1] = collection[i]
counts[collection[i] - collection_min] -= 1
return ordered
def counting_sort_string(string):
"""
>>> counting_sort_string("thisisthestring")
'eghhiiinrsssttt'
"""
return "".join([chr(i) for i in counting_sort([ord(c) for c in string])])
```

Runtime: $O(n)$