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

An integer sorting algorithm that operates by counting the number of objects that have each distinct key value.

Current

Counts

Main Array

Ready to sort

Custom Input (values 0-20)

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

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'.
Blue Highlight: Currently counting this number from input.
Height Increases: Tallying up the frequency.
Final Placement: Moving items to their correct sorted position based on the counts.

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".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep