counting sort

Counting sort is a non-comparison sorting algorithm that orders a collection of integer keys by counting how many times each key value appears, rather than by comparing elements to one another. Because it never compares keys directly, it sidesteps the O(n log n) lower bound that constrains every comparison-based sort.

The algorithm assumes keys drawn from a small range of non-negative integers, no larger than some maximum value k. It runs in three passes over the data:

  • Count: An auxiliary array tallies how many times each key value appears, indexed by the key itself.
  • Accumulate: Each tally becomes a running total, a prefix sum that gives every key its final position in the output.
  • Place: A backward pass over the input writes each element into the slot its cumulative count reserves, then decrements that count.

Iterating in reverse during that final pass keeps equal keys in their original relative order, which makes counting sort stable. That stability is what lets radix sort use it as an inner step to order longer keys one digit at a time.

Step through the visualizer below to watch all three passes on a short list, as the count array turns into a set of positions and each value drops into the slot its running total reserves while equal keys keep their input order:

Interactive diagram — enable JavaScript to view.

Its time complexity is O(n + k) for n items and a key range of k, and its space complexity is likewise O(n + k) for the count and output arrays. Counting sort stays efficient only when k remains close to n. As the key range grows far beyond the number of items, the count array comes to dominate both the running time and the memory the algorithm uses.

Sorting Algorithms in Python

Tutorial

Sorting Algorithms in Python

In this tutorial, you'll learn all about five different sorting algorithms in Python from both a theoretical and a practical standpoint. You'll also learn several related and important concepts, including Big O notation and recursion.

intermediate algorithms python

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated July 29, 2026
Computer Science Glossary Share Feedback