⚙️ DSA: Counting Sort Algorithm

Sorting Integers Without Comparisons

Welcome to another step in your GoNimbus Data Structures and Algorithms (DSA) journey!
In this guide, we’ll explore Counting Sort — a unique algorithm that sorts numbers without comparing them directly.

Counting Sort is particularly efficient when you have many numbers within a small range — and it’s one of the few sorting techniques that doesn’t rely on swapping or recursion.

---

🧩 What Is Counting Sort?

Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each distinct value.

Instead of comparing elements like Bubble Sort, Insertion Sort, or Quicksort, it simply counts how many times each value appears — and then rebuilds the array in sorted order.

💡 Key Idea:
If you know how many times each number appears, you can easily reconstruct the sorted list from smallest to largest.

---

⚡ When to Use Counting Sort

Counting Sort works best when:
✅ You’re sorting non-negative integers
✅ The range of values (k) is not much larger than the number of elements (n)

If the range is too large (for example, sorting values between 1 and 10 million), Counting Sort becomes memory-inefficient.

---

🧠 How Counting Sort Works — Step-by-Step

Let’s take a small array to understand the logic:

myArray = [2, 3, 0, 2, 3, 2]

Step 1️⃣: Find the Range

Find the maximum value in the array.
Here, the max value = 3, so we’ll create a countArray of length max + 1 → [0, 0, 0, 0].

Step 2️⃣: Count the Occurrences

Go through each element in the array and increment the count at that index.

myArray Value	countArray Before	countArray After
2	[0, 0, 0, 0]	[0, 0, 1, 0]
3	[0, 0, 1, 0]	[0, 0, 1, 1]
0	[0, 0, 1, 1]	[1, 0, 1, 1]
2	[1, 0, 1, 1]	[1, 0, 2, 1]
3	[1, 0, 2, 1]	[1, 0, 2, 2]
2	[1, 0, 2, 2]	[1, 0, 3, 2]

✅ After counting, we get:
countArray = [1, 0, 3, 2]

Step 3️⃣: Rebuild the Sorted Array

Now, recreate the sorted list using the count array:

• Value 0 appears 1 time → [0]
• Value 1 appears 0 times → skip
• Value 2 appears 3 times → [0, 2, 2, 2]
• Value 3 appears 2 times → [0, 2, 2, 2, 3, 3]

✅ Sorted Array: [0, 2, 2, 2, 3, 3]

---

🧮 Python Implementation of Counting Sort

Here’s a clean implementation in Python 👇

def countingSort(arr):
    # Step 1: Find maximum value
    max_val = max(arr)
    count = [0] * (max_val + 1)

    # Step 2: Count occurrences
    while len(arr) > 0:
        num = arr.pop(0)
        count[num] += 1

    # Step 3: Rebuild sorted array
    for i in range(len(count)):
        while count[i] > 0:
            arr.append(i)
            count[i] -= 1

    return arr


# Example usage
unsortedArr = [4, 2, 2, 6, 3, 3, 1, 6, 5, 2, 3]
sortedArr = countingSort(unsortedArr)
print("Sorted array:", sortedArr)

Output:

Sorted array: [1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 6]

---

🧭 Understanding the Code

• max_val → Finds the largest number to determine the counting array size.
• count[num] += 1 → Keeps track of how often each number appears.
• The second loop reconstructs the sorted array using those counts.

💡 Since we use array indices to track numbers, Counting Sort only works for non-negative integers.

---

📊 Counting Sort: Time Complexity

Scenario	Time Complexity	Explanation
Best Case	O(n + k)	When the range (k) is small
Average Case	O(n + k)	Efficient if k ≈ n
Worst Case	O(n²) or higher	When k ≫ n (range much larger than dataset)

Space Complexity: O(k)

Because we need an auxiliary array for counting.

---

⚖️ Comparison with Other Sorting Algorithms

Algorithm	Time Complexity	Type	Works On
Bubble Sort	O(n²)	Comparison	Any data type
Insertion Sort	O(n²)	Comparison	Any data type
Quicksort	O(n log n)	Comparison	Any data type
Counting Sort	O(n + k)	Non-Comparison	Integers only

---

🚫 Limitations of Counting Sort

While powerful, Counting Sort has some limitations:

1. ❌ Doesn’t work for negative numbers (since array indices must be non-negative).
2. ❌ Memory inefficient for large ranges (e.g., sorting numbers from 1 to 1,000,000).
3. ⚙️ Limited flexibility — works best for small integer ranges or categorical data.

---

✅ When Counting Sort Shines

• Sorting grades, ages, or categorical data
• When the range (k) is small
• When you need linear-time sorting

For example, sorting student marks between 0–100 is a perfect scenario for Counting Sort.

---

🧠 Visualization Example

Imagine sorting colored balls numbered 0–5:
Instead of comparing them, you just count how many of each color exist — then line them up in order.
That’s exactly what Counting Sort does behind the scenes!

---

📈 Counting Sort Time Complexity Chart

Counting Sort efficiency depends heavily on the ratio of k (range) to n (number of elements):

• 🟢 Best Case (O(n)) – Small range, many numbers
• 🔴 Worst Case (O(n²)) – Large range, few numbers

---

🎯 Key Takeaways

✅ Counting Sort is a non-comparison-based sorting algorithm
✅ Works only for non-negative integers
✅ Time complexity: O(n + k)
✅ Extremely fast for small integer ranges
✅ Not suitable for large or negative datasets

---

🧩 Practice Challenge

Sort the following array manually using Counting Sort logic:

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

Can you figure out what the count array looks like at each step?

---

---