Sorting Algorithm

Counting Sort

A non-comparison sort: instead of comparing elements, it counts how many times each value occurs, then reconstructs the array directly from those counts. It never asks 'is A bigger than B?' — which lets it beat the O(n log n) comparison-sort lower bound whenever the value range k is small.

BestO(n + k)
AverageO(n + k)
WorstO(n + k)
SpaceO(n + k)
StableYes

Try It — Animated Flow

29
8
44
15
3
37
21
Counting sort shines when values fall in a small, known range — here [0, 44]. It counts occurrences instead of comparing.
Step 1 / 24
Pointer / current
Comparing
Swapping / removing
Newly inserted
Settled

Java Implementation

Real-Life Usage

Grading & scoring
Exam scores (0–100) or star ratings (1–5) have a small, known range — counting sort processes thousands of them in one linear pass.
The subroutine inside Radix Sort
Radix sort sorts one digit at a time using counting sort as its stable per-digit step — you can't have one without the other.
Image histograms
Pixel intensities are bounded (0–255 per channel), so building a color histogram — and histogram equalization — is a direct application of counting.
Age or category distributions
Sorting or bucketing records by age, zip-code digit, or any small enumerated category is exactly counting sort's sweet spot.

Trade-offs

Reach for it when
  • The value range k is small and known ahead of time
  • You need a stable, linear-time sort
  • k is not much bigger than n (otherwise the count array wastes memory)
Avoid it when
  • Values span a huge or unknown range (k ≫ n)
  • You're sorting floating-point numbers or arbitrary objects, not small integers
  • Memory for the count array isn't available