AlgoScope

Counting Sort

Count occurrences of each key, prefix-sum the counts, place each element at its final index.

Sorting, algorithm, intermediate
Place 1 at output index 0.0123456789incntout422833100356666771

Counting and Radix Sort: Counting sort, repeated keys

Decision, step 10 of 17

in[6] = 1, key 1. count[1] drops to 0, and that is its slot: out[0] = 1.

Cost

Best
O(n + k)
Average
O(n + k)
Worst
O(n + k)
Space
O(n + k)

k is the key range.

Properties

  • No: Comparison based
  • Yes: Stable
  • No: In place
  • No: Adaptive
  • No: Online

Leads to

Topics that need this one first.

Taught by the same lesson

Counting and Radix Sort covers these too, in the same run.