• +91-9142290450

  • Hajipur, Bihar, 844101

☰
❮
❯

Python Counting Sort

← Previous Next →

Counting sort is a unique sorting algorithm because it doesn’t compare elements like bubble sort, insertion sort or quick sort. Instead, it counts how many times each value appears and uses those counts to build the sorted result. This makes counting sort incredibly fast when the range of values is small and the data is numeric. You’ll often see it used in systems where speed is important and the input values fall within a known limit.

In this tutorial, you’ll learn how counting sort works, why it’s so efficient in the right situations, how to write the algorithm in Python and where the method is used in real-world projects. By the end, you’ll understand the complete flow and know when counting sort is the best choice.

What Is Counting Sort?

Counting sort is a non-comparison sorting algorithm that works by finding the largest value in the list, creating a counting array of size max_value + 1 and storing how many times each number appears. Using this frequency information, it constructs the sorted list.

Since it relies on counting rather than comparing, counting sort can run much faster than many other sorting algorithms, especially when the range of values is small.

How Counting Sort Works Step by Step

Consider this list:

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

Step 1: Find the maximum value

The maximum value is 8, so create a counting array of size 9.

Step 2: Count the occurrences

For each number in the list, increase its count.

The count array becomes:

Index: 0 1 2 3 4 5 6 7 8
Count: 0 1 2 2 1 0 0 0 1

Step 3: Build the sorted list

Repeat each number according to its count:

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

This gives a fully sorted list without a single comparison between elements.

Why Use Counting Sort?

Counting sort has several advantages:

  • Very fast for small value ranges

  • Runs in linear time O(n + k)

  • No element-to-element comparisons

  • Best choice for integers with limited range

  • Often used as a helper step in radix sort

This efficiency makes counting sort a strong option in situations where the values fall within a predictable range.

Counting Sort Algorithm in Python

Here’s the standard implementation of counting sort:

def counting_sort(data):
    if not data:
        return data

    max_val = max(data)
    count = [0] * (max_val + 1)

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

    output = []
    for value, freq in enumerate(count):
        output.extend([value] * freq)

    return output

This code counts each number and rebuilds the list based on frequency.

Example Usage

numbers = [4, 2, 7, 3, 2, 1]
print(counting_sort(numbers))

Output:

[1, 2, 2, 3, 4, 7]

Counting sort gives consistent and accurate results when the input is suitable.

Time Complexity of Counting Sort

Counting sort’s performance depends on the size of the list and the range of values.

  • Best case: O(n + k)

  • Average case: O(n + k)

  • Worst case: O(n + k)

Where

  • n = number of elements

  • k = largest value in the list

Counting sort becomes incredibly fast when k is small compared to n.

When Counting Sort Works Best

Use counting sort when:

  • All values are integers

  • Value range is small or fixed

  • Large datasets need fast sorting

  • Memory is not an issue

  • Input values are non-negative

Systems that handle grades, ages, product IDs or categorised numeric data often rely on this method.

When Counting Sort Is Not Suitable

Avoid counting sort when:

  • The range of values is very large

  • Values include negative numbers (extra handling needed)

  • Memory is limited

  • Sorting needs a comparison-based approach

For example, sorting numbers like 1, 1000, 2000000 with counting sort would waste too much memory.

Real-Life Uses of Counting Sort

Counting sort appears in several practical applications:

Sorting student marks

Marks usually fall within a known range, making counting sort ideal.

Age sorting in demographics

Ages rarely exceed 120, and this small range is perfect for counting.

Character frequency in text processing

Used in algorithms that analyse letters or symbols.

Bucketing categories in surveys

Options are limited, so counting becomes faster.

As a helper in radix sort

Counting sort is often used inside radix sort for digit-level sorting.

Step-by-Step Example

List:

[1, 4, 1, 2, 7, 5, 2]

Step 1: Max → 7
Step 2: Build count array:

[0, 2, 2, 0, 1, 1, 0, 1]

Step 3: Construct sorted list:

[1, 1, 2, 2, 4, 5, 7]

This simple method shows how counting sort avoids comparisons entirely.

Practical Examples

Example 1: Sort numbers

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

Example 2: Sort repeated values

print(counting_sort([5, 3, 5, 3, 5]))

Example 3: Sort zeros and ones

print(counting_sort([0, 1, 1, 0, 1]))

Example 4: Sort small-range floats converted to integers

values = [int(x) for x in [2.1, 3.4, 1.8]]
print(counting_sort(values))

Example 5: Sort ratings from 1–5

ratings = [4, 2, 5, 3, 2, 1]
print(counting_sort(ratings))

Example 6: Sort IDs (0–10)

ids = [3, 7, 0, 10, 5, 3]
print(counting_sort(ids))

Example 7: Sort age values

ages = [12, 15, 12, 18, 15]
print(counting_sort(ages))

Example 8: Sort month numbers

months = [3, 1, 12, 6, 3]
print(counting_sort(months))

Example 9: Sort exam scores

scores = [87, 45, 62, 45]
print(counting_sort(scores))

Example 10: Sort binary list

binary = [1, 0, 1, 0, 1]
print(counting_sort(binary))

Summary of the Tutorial

Counting sort counts how many times each value appears and uses that information to build a sorted list. It works well when the values fall within a small and predictable range. You learned how the algorithm counts frequencies, how to implement it in Python, where it performs best and the practical situations where it is widely used. Counting sort remains one of the fastest options for specialised sorting needs.

Practice Questions

Q1. Write a Python program to sort the list [3, 6, 4, 1, 3, 4, 1, 4] using counting sort.

Q2. Write a Python program to modify counting sort so that it returns a new sorted array instead of modifying the original list.

Q3. Write a Python program to print the count array for the list [0, 2, 2, 3, 1] using counting sort.

Q4. Write a Python program to handle counting sort on a list with values up to 1000.

Q5. Write a Python program to count and display how many times each number appears in the list using counting sort logic.

Q6. Write a Python program to accept a list of integers from user input and sort it using counting sort.

Q7. Write a Python program to sort a list that includes 0 using counting sort.

Q8. Write a Python program to attempt sorting a list with negative numbers using counting sort and observe what breaks.

Q9. Write a Python program to count and print the total number of iterations (loops) made during the counting sort process.

Q10. Write a Python program to compare the output of counting sort with Python's built-in sorted() function for the same list.

← Previous Next →

Try a Short Quiz.

coding learning websites codepractice

No quizzes available.

Python

online coding class codepractice

Introduction to Python

Python Basics

Cotrol Structures

Data Structures

Date and Time

Functions and Module

File Handling

Python OOP

Advanced Concepts

Python DSA

Searching Algorithms

Sorting Algorithms

codepractice logo
Login
Go Back Top