Python Program for Counting Sort Algorithm

A Python program for counting sort uses a count array to tally occurrences of each number, then reconstructs the sorted list; for example, def counting_sort(arr): count = [0] * (max(arr)+1); for num in arr: count[num] += 1; sorted_arr = []; for i, c in enumerate(count): sorted_arr.extend([i]*c); return sorted_arr.

Examples

Input[4, 2, 2, 8, 3, 3, 1]

Output[1, 2, 2, 3, 3, 4, 8]

Input[5, 4, 3, 2, 1]

Output[1, 2, 3, 4, 5]

Input[]

Output[]

How to Think About It

To sort numbers using counting sort, first find the largest number to know the range. Then count how many times each number appears using a list. Finally, build the sorted list by repeating each number according to its count.

Algorithm

1

Find the maximum value in the input list.

2

Create a count list with zeros, sized to max value plus one.

3

Count each number's occurrences by incrementing the count list.

4

Create an empty list for the sorted output.

5

For each index and count in the count list, add the index to the output list count times.

6

Return the sorted output list.

Code

python

def counting_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i, c in enumerate(count):
        sorted_arr.extend([i] * c)
    return sorted_arr

# Example usage
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(sorted_arr)

Output

[1, 2, 2, 3, 3, 4, 8]

Dry Run

Let's trace the list [4, 2, 2, 8, 3, 3, 1] through the counting sort code.

1

Find max value

max_val = 8

2

Initialize count list

count = [0, 0, 0, 0, 0, 0, 0, 0, 0]

3

Count occurrences

After counting: count = [0, 1, 2, 2, 1, 0, 0, 0, 1]

4

Build sorted list

sorted_arr = [1, 2, 2, 3, 3, 4, 8]

Number	Count Array After Increment
4	[0,0,0,0,1,0,0,0,0]
2	[0,0,1,0,1,0,0,0,0]
2	[0,0,2,0,1,0,0,0,0]
8	[0,0,2,0,1,0,0,0,1]
3	[0,0,2,1,1,0,0,0,1]
3	[0,0,2,2,1,0,0,0,1]
1	[0,1,2,2,1,0,0,0,1]

Why This Works

Step 1: Counting occurrences

The code counts how many times each number appears using a list where the index represents the number.

Step 2: Rebuilding sorted list

It then creates the sorted list by repeating each number according to its count, preserving order.

Step 3: Efficiency

Counting sort is efficient for numbers in a small range because it avoids comparisons and uses direct counting.

Alternative Approaches

Using collections.Counter

python

from collections import Counter

def counting_sort_counter(arr):
    count = Counter(arr)
    sorted_arr = []
    for num in range(min(arr) if arr else 0, max(arr) + 1 if arr else 0):
        sorted_arr.extend([num] * count[num])
    return sorted_arr

print(counting_sort_counter([4, 2, 2, 8, 3, 3, 1]))

Uses Python's built-in Counter for counting, simpler but slightly slower for large ranges.

Stable Counting Sort with Output Array

python

def stable_counting_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    output = [0] * len(arr)
    for num in reversed(arr):
        count[num] -= 1
        output[count[num]] = num
    return output

print(stable_counting_sort([4, 2, 2, 8, 3, 3, 1]))

Maintains original order of equal elements, useful for stable sorting but more complex.

Complexity: O(n + k) time, O(k) space

Time Complexity

Counting sort runs in O(n + k) time where n is the number of elements and k is the range of input values, because it counts occurrences and then builds the output.

Space Complexity

It uses O(k) extra space for the count array, which depends on the maximum input value.

Which Approach is Fastest?

The basic counting sort is fastest for small ranges; using Counter is simpler but slower for large ranges; stable counting sort is more complex but preserves order.

Approach	Time	Space	Best For
Basic Counting Sort	O(n + k)	O(k)	Small range integers, simple sorting
Using collections.Counter	O(n + k)	O(k)	Simpler code, moderate range
Stable Counting Sort	O(n + k)	O(n + k)	When stable sorting is needed