Counting Sort Algorithm Explained: A Beginner-Friendly Guide with Examples

In this blog post, we’ll break down the Counting Sort algorithm, how it works, its pros and cons, and walk through examples (with code). Let’s count our way to clarity!

What is Counting Sort?

Counting Sort is a non-comparison-based sorting algorithm used for sorting integers or characters. It works best when the range of input elements is not significantly greater than the number of elements.

📌 Key Idea:

Instead of comparing elements, we:

1. Count how many times each value appears.

2. Use these counts to place elements in the correct order.

Real-Life Analogy

Imagine a classroom where students submit scores (0–100). The teacher creates a count of how many students got each score. Then she prepares the result list using the frequency of each score.

That’s how Counting Sort works—by frequency, not comparison.

Characteristics of Counting Sort

When Should You Use Counting Sort?

✅ When the input consists of integers in a limited range
✅ When you need linear time sorting
✅ When stability matters (like sorting IDs by age)

Step-by-Step: How Counting Sort Works

Let’s say we want to sort the array:

csharp

CopyEdit

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

Step 1: Find the maximum value

• Max = 8
   

Step 2: Create a count array of size (max + 1), initialized to 0:

scss

CopyEdit

[0, 0, 0, 0, 0, 0, 0, 0, 0] (size = 9)

Step 3: Count each element:

• 1 → count[1]++
   
• 2 → count[2]++
   
• 2 → count[2]++
   
• 3 → count[3]++
   
• 3 → count[3]++
   
• 4 → count[4]++
   
• 8 → count[8]++
   

Final count array:

csharp

CopyEdit

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

Step 4: Update count array to get positions:

csharp

CopyEdit

[0, 1, 3, 5, 6, 6, 6, 6, 7]

Step 5: Build output array:

Iterate original array in reverse and place values in the correct position.

Final Sorted Output:

csharp

CopyEdit

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

Counting Sort Algorithm Explained in C

Here’s a simple implementation in C:

c

CopyEdit

#include <stdio.h>

#include <string.h>

void countingSort(int arr[], int n) {

    int output[n];

    int max = arr[0];

    // Step 1: Find max element

    for (int i = 1; i < n; i++)

        if (arr[i] > max)

            max = arr[i];

    // Step 2: Initialize count array

    int count[max + 1];

    memset(count, 0, sizeof(count));

    // Step 3: Store count of each element

    for (int i = 0; i < n; i++)

        count[arr[i]]++;

    // Step 4: Change count[i] to contain actual position

    for (int i = 1; i <= max; i++)

        count[i] += count[i - 1];

    // Step 5: Build output array (stable sort - go in reverse)

    for (int i = n - 1; i >= 0; i--) {

        output[count[arr[i]] - 1] = arr[i];

        count[arr[i]]--;

    }

    // Step 6: Copy output array to original

    for (int i = 0; i < n; i++)

        arr[i] = output[i];

}

int main() {

    int arr[] = {4, 2, 2, 8, 3, 3, 1};

    int n = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, n);

    printf("Sorted array: ");

    for (int i = 0; i < n; i++)

        printf("%d ", arr[i]);

    return 0;

}

Output:

php

CopyEdit

Sorted array: 1 2 2 3 3 4 8

Pros and Cons of Counting Sort

✅ Advantages

• 1. Faster than comparison-based algorithms when the range is small
   
• 2. Stable sorting (order of equal elements is preserved)
   
• 3. Ideal for integer or character sorting
   

❌ Limitations

• 1. Not suitable for very large range of values
   
• 2. Uses extra memory
   
• 3. Not ideal for floating-point numbers or negative numbers (needs adjustment)
   

How to Handle Negative Numbers?

If your array has negative values like [-5, -10, 0, -3], you can:

• 1. Find the minimum value
   
• 2. Offset all values so the smallest becomes 0
   
• 3. Apply Counting Sort
   
• 4. Shift back the sorted values
   

Variants of Counting Sort

1. Radix Sort – uses counting sort as a subroutine

2. Bucket Sort – based on distribution, often combined with counting

3. Character Counting – useful for sorting strings by frequency

Applications of Counting Sort

Learn Sorting Algorithms with Uncodemy

If you're passionate about mastering algorithms like Counting Sort, Merge Sort, Quick Sort, and more—then take the next step by joining the Uncodemy Data Structures and Algorithms Course in Noida.

📘 Course Benefits:

✅ Master 20+ sorting and searching algorithms
✅ Live coding sessions and practical exercises
✅ Interview preparation and mock tests
✅ Certificate + placement support
✅ Learn from top instructors in India

Whether you’re a student or working professional, Uncodemy helps you build coding confidence.

Recap: What Did We Learn?

• 1. Counting Sort is a non-comparison sorting algorithm
   
• 2. Efficient for integers with small range
   
• 3. Time Complexity: O(n + k)
   
• 4. Stable and fast but uses extra space
   
• 5. Ideal for characters, exam scores, limited integers
   
• 6. Not suitable for huge or unbounded ranges
   

Final Thoughts

Counting Sort may not be the most famous algorithm, but it's definitely one of the most clever and efficient when used in the right context. Its non-comparison approach makes it perfect for a variety of applications—from sorting student scores to optimizing time in coding challenges.

Now that you've had Counting Sort algorithm explained with clarity and examples, why not try coding it yourself? And if you're serious about learning more, don’t forget to explore Uncodemy’s DSA course—your path to algorithmic mastery begins here.