Counting Sort Algorithm in DSA Python

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by putting them into labeled boxes for each color, then taking them out in order to get a sorted line of balls.

Unsorted array:
[4, 2, 2, 8, 3, 3, 1]

Count array (index = number):
[0, 1, 2, 2, 1, 0, 0, 0, 1]

Sorted array:
[1, 2, 2, 3, 3, 4, 8]

Dry Run Walkthrough

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

Goal: Sort the list in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input array: [4, 2, 2, 8, 3, 3, 1]
Max value: 8

Why: We need to know how big the count array should be to cover all numbers

Step 2: Create count array of size max+1 and initialize with zeros

Count array: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Why: This array will hold how many times each number appears

Step 3: Count each number's frequency in input array

Count array after counting:
[0, 1, 2, 2, 1, 0, 0, 0, 1]

Why: We record how many times each number occurs to know their positions

Step 4: Modify count array to hold cumulative counts

Cumulative count array:
[0, 1, 3, 5, 6, 6, 6, 6, 7]

Why: Cumulative counts tell the position of each number in the sorted array

Step 5: Place each element from input into output array using count array positions, moving backward

Placing elements:
Output array after placing all: [1, 2, 2, 3, 3, 4, 8]

Why: Placing from the end keeps the sort stable and correct

Result:

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Annotated Code

DSA Python

class CountingSort:
    def sort(self, arr):
        if not arr:
            return arr
        max_val = max(arr)  # find max to size count array
        count = [0] * (max_val + 1)  # initialize count array
        for num in arr:
            count[num] += 1  # count frequency
        for i in range(1, len(count)):
            count[i] += count[i - 1]  # cumulative count
        output = [0] * len(arr)  # output array
        for num in reversed(arr):
            count[num] -= 1  # decrement count for position
            output[count[num]] = num  # place num at correct position
        return output

# Driver code
arr = [4, 2, 2, 8, 3, 3, 1]
sorter = CountingSort()
sorted_arr = sorter.sort(arr)
print(' -> '.join(map(str, sorted_arr)) + ' -> null')

max_val = max(arr) # find max to size count array

determine the range of input values to create count array

count = [0] * (max_val + 1) # initialize count array

prepare count array to hold frequency of each number

for num in arr: count[num] += 1 # count frequency

count how many times each number appears

for i in range(1, len(count)): count[i] += count[i - 1] # cumulative count

transform counts to cumulative counts to find positions

for num in reversed(arr): count[num] -= 1 # decrement count for position output[count[num]] = num # place num at correct position

place elements in output array in stable order using counts

Output

1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 8 -> null

Complexity Analysis

Time: O(n + k) because we count frequencies in O(n) and create count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Compared to comparison sorts like quicksort O(n log n), counting sort is faster when k (range) is not much larger than n

Edge Cases

empty array

returns empty array immediately without error

DSA Python

if not arr:
    return arr

array with one element

returns the same single-element array

DSA Python

handles normally as max and count arrays are created

array with all elements the same

count array counts one number, output array returns same repeated elements

DSA Python

count[num] += 1 counts correctly even if all same

When to Use This Pattern

When you need to sort integers with a known small range quickly and without comparisons, reach for counting sort because it uses counting and positions instead of comparing elements.

Common Mistakes

Mistake: Not using cumulative counts to find correct positions
Fix: Add a loop to convert count array to cumulative counts before placing elements

Mistake: Placing elements in output array in forward order causing unstable sort
Fix: Place elements by iterating input array backward to maintain stability

Mistake: Not handling empty input array causing errors
Fix: Add a guard clause to return early if input is empty

Summary

Counting sort sorts numbers by counting their occurrences and using these counts to place them in order.

Use counting sort when sorting integers with a limited range efficiently and stably.

The key insight is to use a count array to track frequencies and cumulative counts to find exact positions without comparing elements.

Practice

1. What is the main idea behind the Counting Sort algorithm?

easy

A. Swapping adjacent elements if they are in wrong order

B. Comparing each element with every other element to sort

C. Dividing the list into halves and sorting recursively

D. Counting the occurrences of each element and using that to place elements in order

Solution

1. Step 1: Understand Counting Sort principle

   Counting Sort counts how many times each value appears in the list.

2. Step 2: Use counts to place elements

   It then uses these counts to place elements directly in the sorted order without comparisons.

3. Final Answer:

   Counting the occurrences of each element and using that to place elements in order -> Option D

4. Quick Check:

   Counting occurrences = A [OK]

Hint: Counting Sort uses counts, not comparisons, to sort [OK]

Common Mistakes:

• Thinking Counting Sort compares elements
• Confusing Counting Sort with comparison-based sorts
• Assuming Counting Sort works on all data types

2. Which of the following is the correct way to initialize the count array for Counting Sort in Python for input values ranging from 0 to 5?

easy

A. count = [0] * 6

B. count = [0] * 5

C. count = [null] * 6

D. count = []

Solution

1. Step 1: Determine count array size

   For values 0 to 5 inclusive, we need 6 slots (0,1,2,3,4,5).

2. Step 2: Initialize count array with zeros

   Using [0] * 6 creates a list of six zeros to count occurrences.

3. Final Answer:

   count = [0] * 6 -> Option A

4. Quick Check:

   Length 6 with zeros = D [OK]

Hint: Count array size = max value + 1 [OK]

Common Mistakes:

• Using wrong size for count array
• Initializing with null instead of 0
• Leaving count array empty

3. What will be the output of the following Python code using Counting Sort on the list [4, 2, 2, 8, 3, 3, 1]?

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

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

medium

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

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

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

D. [0, 1, 2, 2, 3, 3, 4, 8]

Solution

1. Step 1: Count occurrences of each number

   Count array for max_val=8: counts for 1=1, 2=2, 3=2, 4=1, 8=1, others=0.

2. Step 2: Build sorted list using counts

   Extend sorted_arr with each number repeated by its count: [1, 2, 2, 3, 3, 4, 8].

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option A

4. Quick Check:

   Sorted list matches counting sort output = B [OK]

Hint: Counting Sort output is sorted list with duplicates in order [OK]

Common Mistakes:

• Forgetting to repeat elements by their count
• Returning unsorted or reversed list
• Including zeros for missing elements

4. The following code attempts to implement Counting Sort but has a bug. What is the error?

def counting_sort_bug(arr):
    max_val = max(arr)
    count = [0] * max_val
    for num in arr:
        count[num] += 1
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

print(counting_sort_bug([3, 1, 2, 3]))

medium

A. Count array initialized with zeros incorrectly

B. Loop to build sorted_arr uses wrong range

C. Count array size is too small, missing last element count

D. Function does not return anything

Solution

1. Step 1: Check count array size

   Count array size is max_val, but should be max_val + 1 to include max element index.

2. Step 2: Understand impact on counting

   Missing last index causes error when counting max element (3), leading to IndexError or wrong counts.

3. Final Answer:

   Count array size is too small, missing last element count -> Option C

4. Quick Check:

   Count array size = max_val + 1 [OK]

Hint: Count array size must be max value + 1 [OK]

Common Mistakes:

• Using max_val instead of max_val + 1 for count array size
• Ignoring IndexError from out-of-range access
• Not initializing count array properly

5. You have a list of exam scores ranging from 0 to 100, but some scores are missing. How can you modify Counting Sort to efficiently sort this list and also find how many students scored exactly 75?

hard

A. Use a comparison sort and count 75s during sorting

B. Use Counting Sort normally, then check count[75] for number of students scoring 75

C. Sort with Counting Sort and then scan sorted list to count 75s

D. Use Counting Sort but ignore counts for missing scores

Solution

1. Step 1: Apply Counting Sort on scores 0-100

   Create count array of size 101, count occurrences of each score.

2. Step 2: Use count array to find number of 75 scores

   Count at index 75 directly gives number of students scoring 75 without scanning sorted list.

3. Final Answer:

   Use Counting Sort normally, then check count[75] for number of students scoring 75 -> Option B

4. Quick Check:

   Counting array index = score count, access directly [OK]

Hint: Counting array index = score count, access directly [OK]

Common Mistakes:

• Scanning sorted list instead of using count array
• Ignoring missing scores in count array
• Using slower comparison sorts unnecessarily