this is pure python implementation of counting sort algorithm for doctests run following command python m doctest v countingsort py or python3 m doctest v countingsort py for manual testing run python countingsort py pure implementation of counting sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples countingsort0 5 3 2 2 0 2 2 3 5 countingsort countingsort2 5 45 45 5 2 if the collection is empty returns empty get some information about the collection create the counting array count how much a number appears in the collection sum each position with it s predecessors now countingarri tells us how many elements i has in the collection create the output collection place the elements in the output respecting the original order stable sort from end to begin updating countingarr countingsortstringthisisthestring eghhiiinrsssttt test string sort pure implementation of counting sort algorithm in python param collection some mutable ordered collection with heterogeneous comparable items inside return the same collection ordered by ascending examples counting_sort 0 5 3 2 2 0 2 2 3 5 counting_sort counting_sort 2 5 45 45 5 2 if the collection is empty returns empty get some information about the collection create the counting array count how much a number appears in the collection sum each position with it s predecessors now counting_arr i tells us how many elements i has in the collection create the output collection place the elements in the output respecting the original order stable sort from end to begin updating counting_arr counting_sort_string thisisthestring eghhiiinrsssttt test string sort
def counting_sort(collection):
    
    
    if collection == []:
        return []

    
    coll_len = len(collection)
    coll_max = max(collection)
    coll_min = min(collection)

    
    counting_arr_length = coll_max + 1 - coll_min
    counting_arr = [0] * counting_arr_length

    
    for number in collection:
        counting_arr[number - coll_min] += 1

    
    
    for i in range(1, counting_arr_length):
        counting_arr[i] = counting_arr[i] + counting_arr[i - 1]

    
    ordered = [0] * coll_len

    
    
    for i in reversed(range(coll_len)):
        ordered[counting_arr[collection[i] - coll_min] - 1] = collection[i]
        counting_arr[collection[i] - coll_min] -= 1

    return ordered


def counting_sort_string(string):
    
    return "".join([chr(i) for i in counting_sort([ord(c) for c in string])])


if __name__ == "__main__":
    
    assert counting_sort_string("thisisthestring") == "eghhiiinrsssttt"

    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(counting_sort(unsorted))