Counting Sort

Mental Model:

Get range of collection
Create counts array (of length equal to range)
Count occurrences of each element i and store in counts[i]
Sum each position of the element with predecessors.

💡

Now, counts[i] shows # of elements <= i in the collection

Create an output array
Populate the output such that:

💡

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)$