@@ -0,0 +1,1269 @@
+%22%22%22%0ACounting sort algorithm.%0A%0AUseful for sorting sequences of integers up to a relatively small number K.%0ATo generalize, counting sort can be useful for sorting sequences of a relatively%0Asmall number of different values, when we have a sequence of all possible values%0A(in sorted order).%0A%0AThe complexity of counting sort for a sequence of N elements with K possible%0Adifferent values for each element is O(N * K).%0A%0AExample:%0A---%0A%0ASort the list %5B'c', 'd', 'd', 'a', 'c', 'c', 'b', 'a', 'c', ... %5D knowing that%0Aall elements have values in: ('a', 'b', 'c', 'd').%0A%0AIf the length N of the list is: %60N %3E 2%5E4%60 (i.e. %60log(N) %3E 4%60), counting sort%0Awill be faster than comparison-sorting algorithms (which have complexity of%0AO(N * log(N)).%0A%22%22%22%0A%0A%0Afrom collections import Counter%0A%0A%0A__all__ = %5B'sort'%5D%0A%0A%0Adef sort(sequence, values):%0A    %22%22%22%0A    Sort using the counting sort algorithm.%0A    %0A    sequence -- the sequence to sort%0A    values -- all the possible values of elements in the sequence%0A              (values must be in sorted order)%0A    %0A    Returns a list with the given sequence's elements in non-decreasing order.%0A    %22%22%22%0A    count_per_value = Counter(sequence)%0A    result = %5B%5D%0A    for value in values:%0A        result.extend(%5Bvalue%5D * count_per_value%5Bvalue%5D)%0A    return result%0A

Add counting sort algorithm