When should I use Counting Sort?

Use it when the range of input values (k) is not significantly larger than the number of elements (n). It is ideal for sorting integers within a small range.

Is Counting Sort stable?

Yes, our implementation follows the stable version of Counting Sort by processing elements from right to left using cumulative counts.

What is the time complexity of Counting Sort?

It is O(n + k), where n is the number of elements and k is the range of input values.

Counting Sort

Counting sort is an integer sorting algorithm that counts the number of objects having each distinct key value.

Intuition

Imagine you have a bag of colored balls. Instead of comparing them (Red vs Blue), you simply count them: 3 Reds, 2 Blues, 5 Greens. Then you can easily line them up: Red, Red, Red, Blue, Blue, Green... Counting Sort works this way for numbers.

Concept

No Comparisons: Unlike Bubble or Merge Sort, it doesn't compare elements against each other.
Frequency Count: It counts occurrences of each unique value.
Key Constraint: Efficient only when the range of values difference (k) is not significantly larger than the number of items (n).

How it Works

Algorithm:

Find the range (Max value).
Initialize a 'Count Array' of size (Max+1) with zeros.
Iterate input and increment the count for each number.
Modify Count Array to store cumulative sums (this helps place elements directly).
Place elements from the input array into the output array based on these cumulative positions.

Step-by-Step Breakdown

Watch the visualization:

Secondary Bar Chart: Represents the 'Count Array'.
Amber bar: The input element being read: while finding the maximum, while counting, and while placing it.
Height Increases: Tallying up the frequency.
Blue bar: The value just copied back into the array.
Green bars: The part of the array already copied back in sorted order.

When to Use

Small Integers: Perfect when sorting integers within a specific, small range (e.g., ages, test scores 0-100).
Linear Time Needed: When O(n log n) is too slow and the range allows O(n).

When NOT to Use

Large Range: If you have [1, 10, 1000000], the count array is huge and sparse. Bad space complexity.
Non-Integers: Cannot sort strings or floats directly without mapping.

How to Identify

"Sort an array of integers with small range", "O(n) sorting".

Sample Problems

Sort Array (Counting Sort)

Counting sort is a valid strategy if constraints on values are small.

Relative Sort Array

Counting sort is ideal for counting frequencies of reference elements.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Shell Sort

Radix Sort