def counting_sort(items, key=None, max_key=None, min_key=None):
    """
    Sorts an array of items by their integer keys, using counting_sort.
    Implemented as a stable sort.

    This is a modified version of the code described on Wikipedia:
    https://en.wikipedia.org/wiki/Counting_sort

    Parameters
    ----------
    items: list of items
    key: function mapping each item to an integer key
    max_key: the maximum possible key
    min_key: the minimum possible key
    """
    #If no key functions is passed, assume items
    #are integers in the range 0,1,2,...,max_key
    if key is None:
        key = lambda x: x

    #If the maximum key wasn't specified, find it.
    if max_key is None:
        #If min_key is also none, find both simultaneously.
        if min_key is None:
            max_key = min_key = key(items[0])
            for item in items[1:]:
                next_key = key(item)
                if next_key < min_key:
                    min_key = next_key
                elif next_key > max_key:
                    max_key = next_key
        else:
            #(Takes time n if max_key was not specified)
            max_key = max(key(item) for item in items)
    #If None was passed for the minimum key, find the minimum.
    elif min_key is None:
        #(Takes time n if min_key was set to None)
        min_key = min(key(item) for item in items)

    #Initialize an array to count the occurrances of keys.
    #The index is the key, and counts[key] is the count of that key.
    #(Takes time K)
    counts = [0 for k in range(max_key-min_key+1)]

    #In case the minimum key is not 0, redefine the key function to return
    #values from 0 to max_key-min_key, in order to index into the
    #counts array.
    shifted_key = lambda x: key(x) - min_key

    #Iterate through items, to count how many times each key occurs
    #(Takes time n)
    for item in items:
        counts[shifted_key(item)] += 1

    #Rename the counts array because we will be overwriting it to store indices
    #of keys instead of counts of keys.
    index_of = counts

    #Create the index_of array as the cumulative sum of the counts array.
    #When the loop finishes, we will have
    #index_of[k] = counts[0] + counts[1] + ... + counts[k-1],
    #but we can do it in place, replacing count[k] with index_of[k].
    #
    #The value index_of[k] is the start index of the items with key(item) = k.
    #In the final loop, we will increment index_of[k] each time we place an
    #item with key(item) = k, so that the next time k is encountered, we'll
    #have the new correct index for that key.

    index=0 #Store the current index (cumulative sum of counts)
    #(Takes time K)
    for k, count in enumerate(counts):
        #k is the shifted key, count is its count.
        index_of[k] = index #Note that index_of = counts
        index += count

    #Create a new array for output. We can't modify the input in place
    #if we want a stable sort.
    #(Takes time n)
    output = [None for _ in range(len(items))]

    #Iterate through items, putting each item in the correct place in output.
    #The index for the first item with each key k is stored in index_of[k]
    #(Takes time n)
    for item in items:
        #Put the item in the correct index for its key.
        output[index_of[shifted_key(item)]] = item
        #Increment the index for the next time we encounter the key.
        index_of[shifted_key(item)] += 1


    #Total runtime in iterations is 2k + 3n, plus another n if max_key or min_key
    #is not specified.
    return output