Counting Sort

Characteristics

Non negative integers with a known maximum value

Counting sort can be applied if the input numbers are in the set {0, 1, .. ,k}, a set of non negative integers with a maximum value k.

No comparisons between elements

There are no comparisons between input elements that take place in counting sort. It uses array indexing to determine the relative order of the input numbers. It identifies the relative positions of each input element. For each element x, counting sort counts number of elements less than x. Then it uses this information to place element x directly into its correct position.

Linear time complexity

It has a linear time complexity.

• Worst Time complexity (Big-O): O(k+n), where k: maximum value of the integer set and n: total number of integers in the set.
  
• Average Time complexity (Big-Theta): Θ(k+n), where k: maximum value of the integer set and n: total number of integers in the set.
  
• Best Time complexity (Big-Omega): Ω(k+n), where k: maximum value of the integer set and n: total number of integers in the set.
  
• Space complexity: O(k+n), where k: maximum value of the integer set and n: total number of integers in the set.

Stable

Counting sort is stable. Numbers with the same value appears in the output array as they appear in the input array. Let's take an input array A = [3, 0, 3] and k = 3. In the input array the value 3 occurs 2 times; at index 0 and 2. Counting sort ensures that in the output array the occurrences of 3 are placed as same order as of the input array.

Algorithm Pseudocode

Counting_Sort(A, k)
    let R[0 .. A.length-1] be a new array
    for i=0 to A.length-1
        R[i] = 0
    let C[0 .. k] be a new array
    for i=0 to k
        C[i] = 0
    for i=0 to A.length-1
        C[A[i]] = C[A[i]]+1
    for i=1 to k
        C[i] = C[i-1] + C[i]
    for i=A.length-1 to 0
        R[C[A[i]]] = A[i]
        C[A[i]] = C[A[i]] - 1

Implementation using Python 3

"""
Implementation of counting sort with test cases
"""

def get_sorted_list(numbers, max_value):
    """ Returns sorted list of numbers using counting sort algorithm.

        Arguments:
        numbers -- list of integers, non negative and less than max_value
        max_value -- integer
    """
    sorted_numbers = [None] * len(numbers)
    counts = [0] * (max_value+1)
    for i in numbers:
        counts[i] += 1
    counts[0] -= 1
    for i in range(1, max_value+1):
        counts[i] += counts[i-1]
    for i in numbers[::-1]:
        sorted_numbers[counts[i]] = i
        counts[i] -= 1
    return sorted_numbers

if __name__ == "__main__":
    A = [1, 5, 0, 0, 3, 3, 2, 1, 1]
    k = 5
    expected = [0, 0, 1, 1, 1, 2, 3, 3, 5]
    assert expected == get_sorted_list(A, k), "Failed on A={}, k={}".format(A, k)

    A = [9, 7]
    k = 9
    expected = [7, 9]
    assert expected == get_sorted_list(A, k), "Failed on A={}, k={}".format(A, k)

Practice challenges

Easy difficulty challenges:

• Counting Sort 1 - Hackerrank
• Counting Sort 2 - Hackerrank

Medium difficulty challenges:

• The Full Counting Sort - Hackerrank

Reference

• Introduction to algorithms by Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford
• Timsort Wikipedia article
• Counting sort Wikipedia article
• timeit module documentation