mastorna.it
IT

Sorting algorithms · 5/7

Counting sort

Replaces comparisons with counts of integer keys.

Average timeΘ(n + k) SpaceΘ(n + k) StableYes In placeNo

How it works

Counts become cumulative positions; scanning input right to left creates stable output.

Invariant: After accumulation C[v] counts items ≤ v; while emitting, it points to the next free position for v.

Step-by-step visualization

Each bar represents one element. Colors identify compared elements, the pivot or key, the final region and the active range.

Use 2 to 16 values from 0 to 999, spanning a range no wider than 80.

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison pivot / key final

Pseudocode linked to the visualization

  1. C[0 … k] ← 0
  2. for value in A: C[value]++
  3. for i ← 1 to k: C[i] ← C[i] + C[i − 1]
  4. for i ← n − 1 downto 0
  5. B[C[A[i]] − 1] ← A[i]
  6. C[A[i]]--
  7. copy B into A

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(n + k)

Reading n items and initializing k counters is necessary: Θ(n+k).

Average caseΘ(n + k)

Input order does not change the passes: Θ(n+k).

Worst caseΘ(n + k)

Worst case performs the same linear passes.

Auxiliary spaceΘ(n + k)

Θ(k) counters and Θ(n) stable output: Θ(n+k), not in place.

Properties at a glance

Stable

Stability concerns the relative order of elements with equal keys.

Not in place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Excellent for integers whose range k is not much larger than n.

Common mistake

A huge max−min range wastes time and memory. This visualizer accepts nonnegative integers.