DSA Counting Sort

🔢 DSA Counting Sort – Complete Beginner Guide

(Concept • Manual Run-Through • Algorithm • Code • Time Complexity)

Counting Sort is a non-comparison based sorting algorithm.
It is very fast when the range of input values is small.

1️⃣ What is Counting Sort?

Counting Sort:

Counts how many times each value appears
Uses this count to place elements in the correct sorted position
Does not compare elements like Bubble or Quick Sort

📌 Best suited when:

Values are non-negative integers
Range of values is not very large

2️⃣ Simple Idea (One Line)

Count occurrences → calculate positions → build sorted array

3️⃣ When Should We Use Counting Sort?

✔ Small range of numbers (e.g., 0–100)
✔ Large number of elements
❌ Very large value range
❌ Floating-point or negative numbers (without modification)

4️⃣ Counting Sort – Manual Run-Through

🔹 Given Array

Step 1: Find Maximum Value

Step 2: Create Count Array

Size = max + 1 = 9

Step 3: Count Occurrences

Step 4: Build Sorted Array

Write numbers based on their count:

✅ Final Sorted Array

5️⃣ Counting Sort Algorithm (Steps)

Find maximum element in array
Create count array of size max + 1
Count frequency of each element
Reconstruct sorted array using count array

6️⃣ Pseudocode

7️⃣ Counting Sort Implementation (C++)

#include <iostream>
using namespace std;int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
int n = 7;

int max = arr[0];
for(int i = 1; i < n; i++) {
if(arr[i] > max)
max = arr[i];
}

int count[max + 1] = {0};

for(int i = 0; i < n; i++) {
count[arr[i]]++;
}

int index = 0;
for(int i = 0; i <= max; i++) {
while(count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}

for(int i = 0; i < n; i++) {
cout << arr[i] << " ";
}

return 0;
}

#include <iostream>

using namespace std;int main() {

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

int n = 7;

int max = arr[0];

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

if(arr[i] > max)

max = arr[i];

}

int count[max + 1] = {0};

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

count[arr[i]]++;

}

int index = 0;

for(int i = 0; i <= max; i++) {

while(count[i] > 0) {

arr[index++] = i;

count[i]--;

}

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

cout << arr[i] << " ";

}

return 0;

}

Output

8️⃣ Stable Counting Sort (Advanced Idea)

To make Counting Sort stable:

Use prefix sum of count array
Traverse input from right to left

📌 This is used in Radix Sort.

9️⃣ Time Complexity

Let:

n = number of elements
k = range of values (max value)

⏱ Complexity

Case	Time Complexity
Best	O(n + k)
Average	O(n + k)
Worst	O(n + k)

📌 Much faster than O(n²) sorting when k is small.

🔟 Space Complexity

Metric	Value
Extra Space	O(k)
Reason	Count array

1️⃣1️⃣ Advantages of Counting Sort

✔ Very fast
✔ Linear time complexity
✔ Stable (with prefix sum method)
✔ No comparisons

1️⃣2️⃣ Disadvantages of Counting Sort

❌ Extra memory required
❌ Not suitable for large ranges
❌ Only works with integers
❌ Not in-place

1️⃣3️⃣ Counting Sort vs Comparison Sorts

Algorithm	Time Complexity	Comparison Based
Bubble	O(n²)	✅
Quick	O(n log n)	✅
Counting	O(n + k)	❌

Exam / Interview Questions (Counting Sort)

Q1. Is Counting Sort comparison based?
👉 No

Q2. When is Counting Sort fastest?
👉 When range of values is small

Q3. Is Counting Sort stable?
👉 Yes (with prefix sum method)

Q4. Where is Counting Sort used?
👉 As part of Radix Sort

Final Summary

✔ Counting Sort uses frequency counting
✔ No element comparisons
✔ Time complexity: O(n + k)
✔ Requires extra memory
✔ Best for small integer ranges
✔ Important for exams & competitive programming

DSA Counting Sort