Counting Sort

Idea

Go through all the N elements and index it into the hash table.
Go through the k-element hash table and put elements back into the array.

Pseudocode

def COUNTING_SORT(INPUT_ARR):
    hash_table = HASH_INIT(max(INPUT_ARR))
    for each element in INPUT_ARR
        hash_table.add(element)
    for each element in hash_table
        OUTPUT_ARR[index] = element
        increment index
    return OUTPUT_ARR

Big-O Analysis

N - Number of elements in the INPUT_ARR

[0...K] - Range of input values

Time Complexity is - O(N+K) - looping through the input array and looping through the hash table

Space Complexity is - O(K) to store the hash table

Properties

• Counting sort is a stable sort. ie Numbers with the same value appear in the output array in the same order.
• Counting sort is used as a subroutine of radix sort.

Things to think about

• Given n integers in range 0 to k, optimize a search query about how many inputs fall within range [a...b]?