Counting Sort & Radix Sort

In the previous lesson, we learned about Heap Sort, a comparison-based sorting algorithm with guaranteed performance.

So far, all sorting algorithms we studied worked by comparing elements with each other.

In this lesson, we explore a different idea — non-comparison-based sorting.

Counting Sort and Radix Sort do not compare elements directly. Instead, they use the properties of numbers to sort faster in specific situations.

Why Non-Comparison Sorting Matters

Comparison-based sorting algorithms have a theoretical lower bound of O(n log n).

This means no matter how clever the algorithm is, it cannot be faster than O(n log n) in the general case.

Counting Sort and Radix Sort break this limitation by avoiding comparisons entirely.

Counting Sort – Core Idea

Counting Sort works by counting how many times each value appears in the input.

Instead of moving elements based on comparisons, it places them directly into their correct positions using counts.

This makes Counting Sort extremely fast when the range of input values is small.

When Counting Sort Works Best

Counting Sort is ideal when:

• All values are non-negative integers
• The maximum value is not too large
• Memory usage is acceptable

It is commonly used for sorting: student marks, ages, ratings, IDs, and frequencies.

Counting Sort Algorithm (Code)

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)

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

    index = 0
    for i in range(len(count)):
        while count[i] > 0:
            arr[index] = i
            index += 1
            count[i] -= 1

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

This algorithm runs in O(n + k), where k is the range of values.

Limitations of Counting Sort

Counting Sort is not suitable for large value ranges.

For example, sorting values up to one billion would require massive memory.

This limitation leads us to a more powerful idea: Radix Sort.

Radix Sort – Sorting Digit by Digit

Radix Sort processes numbers one digit at a time.

It starts with the least significant digit and moves toward the most significant digit.

At each step, it uses a stable sorting algorithm (usually Counting Sort).

Real-World Analogy

Think of sorting phone numbers.

Instead of comparing full numbers, we group them by last digit, then second last digit, and so on.

After processing all digits, the list becomes fully sorted.

Radix Sort Algorithm (Code)

def counting_sort_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_digit(arr, exp)
        exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

Radix Sort achieves O(d × (n + k)) time, where d is the number of digits.

Counting Sort vs Radix Sort

Counting Sort is simpler but limited by value range.

Radix Sort handles large numbers by breaking them into digits.

Both algorithms are stable and non-comparison-based.

Mini Practice

Think about these scenarios:

• Sorting student ages from 1–100
• Sorting large phone numbers

Which algorithm fits each case best?

Exercises

Quick Quiz

In the next lesson, we will move from sorting to searching and explore Linear Search as the foundation of search algorithms.