Counting Sort Visualizer

How it works

1. Find the smallest value lo and the range k = max − lo + 1; create a count array C of k zeros.
2. Count: for each element, add 1 to C[A[i] − lo].
3. Prefix sums: for v = 1 … k − 1, C[v] += C[v − 1]. Now C[v] is how many elements are ≤ that value — one past the last slot the value will occupy.
4. Place: walk A from right to left; for each element, decrement its counter and write the element to B[C[v]].
5. Copy the output array B back into A.

Worked example: sorting [5, 2, 7, 2, 4, 5, 1, 3]

The visualizer above opens on this array: eight values from 1 to 7, so k = 7.

• Count: C for the values 1…7 is [1, 2, 1, 1, 2, 0, 1] — two 2s, two 5s and no 6.
• Prefix sums: [1, 3, 4, 5, 7, 7, 8]. Read it as “3 elements are ≤ 2”, so the two 2s fill output slots 1 and 2 (0-based).
• Place, right to left: 3 → slot 3, 1 → slot 0, the second 5 → slot 6, 4 → slot 4, the second 2 → slot 2, 7 → slot 7, the first 2 → slot 1, the first 5 → slot 5.
• Output: [1, 2, 2, 3, 4, 5, 5, 7] after 8 writes and zero comparisons.

Look at the duplicates: the second 2 is placed first, into the later of the two slots, so the two 2s keep their input order. That is the whole reason the placing loop runs right to left.

How counting sort beats O(n log n)

The Ω(n log n) lower bound only applies to algorithms that learn about the order by comparing pairs of elements. Counting sort never compares: it uses each value as an index into C, so one array access does the work that would otherwise take about log n comparisons.

The cost moves into the size of C instead. Counting is O(n), the prefix sums O(k) and placing O(n), so the total is O(n + k) in every case, whatever the order of the input.

When counting sort is — and isn't — a good idea

Counting sort shines when k is no bigger than about n: exam scores 0–100, ages, star ratings, bytes 0–255, small enum values. It is a poor choice when the range dwarfs the number of elements — sorting five arbitrary 32-bit integers could need a count array with over four billion entries. Floating-point numbers and strings don't fit directly either.

When the range is too wide to draw, the visualizer switches to a sparse view that hides zero counts, but the algorithm still allocates and scans all k counters — that is the hidden cost.

Stability, memory and radix sort

As written here counting sort is stable: placing from right to left puts the last copy of each value into the last slot of its block. Stability is more than a nicety — it is what lets a counting pass serve as the per-digit step inside radix sort, which sorts large integers one digit at a time.

It is not in-place: it needs the count array (O(k)) and an output array (O(n)). A simpler variant just writes each value C[v] times and needs no output array, but it only works for bare integers — it can't carry along the record each key belongs to.

Common mistakes and interview tips

• Sizing C as max + 1 instead of max − min + 1. It wastes memory and breaks on negative numbers; offsetting by lo fixes both.
• Placing from left to right with the prefix sums. The output is still sorted, but equal keys come out reversed — unstable, which silently breaks radix sort.
• An off-by-one in the place step: decrement the counter before writing, because the prefix sum points one past the block's last slot.
• Interview angle: “sort an array of 0s, 1s and 2s” or “sort a million ages” — counting sort is the O(n) answer.

Time and space complexity

Counting Sort in Python

def counting_sort(A):
    # Stable counting sort of integers: O(n + k) time and extra space,
    # where k = max(A) - min(A) + 1. Indexing C by A[i] - lo makes
    # negative numbers work too. Only worth it when k is small.
    n = len(A)
    if n == 0:
        return
    lo = min(A)
    k = max(A) - lo + 1
    C = [0] * k                         # C[v] counts the value v + lo
    B = [0] * n                         # output array
    for i in range(n):                  # 1) count every value
        C[A[i] - lo] += 1
    for v in range(1, k):               # 2) prefix sums: end of v's block
        C[v] += C[v - 1]
    for i in range(n - 1, -1, -1):      # 3) place right -> left (stable)
        v = A[i] - lo
        C[v] -= 1
        B[C[v]] = A[i]
    A[:] = B                            # copy B into A

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Radix Sort VisualizerRadix sort orders integers digit by digit — ones, then tens, then hundreds — using stable bucket passes. Watch LSD radix sort animated, with Python code.
• Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
• Insertion Sort VisualizerInsertion sort takes each element and slides it left into place in the sorted prefix. Watch every shift animated, with Python code and O(n²) complexity.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.