Sorting · Intermediate

Count each key.
Place without comparing.

Counting Sort replaces pairwise comparisons with a compact table of integer-key frequencies, then turns those counts into exact output positions.

Start visualizing How it works

Mini example[ 2, 0, 1, 2 ]

2012

read keys

112

frequencies

0122

placed

Key idea Its speed depends on both n values and k possible keys, so a small dense range is the superpower.

Before you start

What you will learn

A clear finish line for the lesson, plus the small amount of knowledge you need before beginning.

Learning objectives

Explain why Counting Sort needs integer keys from a manageable range.
Build a frequency table using a minimum-value offset.
Transform frequencies into cumulative ending positions.
Trace stable right-to-left placement into an output array.

Prerequisites

Array indexing and integer arithmetic
Frequency tables and prefix sums
Big O notation with more than one input variable

Review the foundations glossary →

01Understand02Visualize03Trace04Code05Complexity06Quiz07Challenge08Use cases

01 — The idea

Turn values into addresses

What if each integer can point directly to the bucket that describes where it belongs?

-2v - min0

Create one bucket per key

Find the minimum and maximum, then offset each value so even negative integers map to indexes starting at zero.

124

Count and accumulate

Record every frequency, then add counts from left to right so each bucket knows how many values end at or before its key.

12A2B

Place from right to left

Use each cumulative count as the next output position. Reverse scanning preserves the order of records with equal keys.

02 — Try it yourself

Watch frequencies become positions

Follow each value into a bucket, see prefix totals form, and place labeled duplicates into a stable output.

Your array

3–10 integers from -9 to 12; key range ≤ 20

Phase CountKey range k 8 Paused

Input valuesscan left to right

402A12B2833A43B516

Frequency bucketsindex = key - minimum

key 10bucket 0

key 20bucket 1

key 30bucket 2

key 40bucket 3

key 50bucket 4

key 60bucket 5

key 70bucket 6

key 80bucket 7

Stable output0 of 7 placed

·0·1·2·3·4·5·6

Minimum: 1Maximum: 8Mapping: value - minimum

Create 8 buckets for keys 1 through 8.

Speed

Values counted0

Writes0

Placements0

Active value Active bucket Output

Dry-run trace

Turn each animation into a written decision

The latest eight Counting Sort decisions
Step	Pass	Action	Value / bucket	Current output	Writes
0	Count	Create buckets	—	`[·, ·, ·, ·, ·, ·, ·]`	0

The highlighted row always matches the visualization above. Step forward to extend the trace.

03 — Read the code

From frequencies to stable code

Compare the same minimum offset, prefix counts, and reverse placement across all four languages.

01export function countingSort(numbers) {02  if (numbers.some((value) => !Number.isInteger(value))) throw new TypeError("Integers required");03  if (numbers.length === 0) return [];04 05  const minimum = Math.min(...numbers);06  const maximum = Math.max(...numbers);07  const counts = Array(maximum - minimum + 1).fill(0);08 09  for (const value of numbers) counts[value - minimum] += 1;10  for (let index = 1; index < counts.length; index += 1) {11    counts[index] += counts[index - 1];12  }13 14  const output = Array(numbers.length);15  for (let index = numbers.length - 1; index >= 0; index -= 1) {16    const value = numbers[index];17    counts[value - minimum] -= 1;18    output[counts[value - minimum]] = value;19  }20  return output;21}

04 — Avoid the traps

Common mistakes

These bugs often produce an answer that looks almost right. Learn the symptom and the correction together.

Ignoring the key range

Symptom: Sorting a few widely separated values allocates a huge count array.

Correction: Check k = maximum - minimum + 1. Use a comparison sort when k is large relative to n.

Using values directly as indexes

Symptom: Negative values create invalid indexes or end up in the wrong bucket.

Correction: Map value v to bucket v - minimum, then add minimum back only when interpreting the key.

Placing equal records left to right

Symptom: Equal-key records appear in reverse relative order even though the counts are correct.

Correction: After cumulative counts, scan the original input from right to left for stable placement.

06 — Mini game

Build the frequency table

Read each incoming value and click the bucket whose key matches it.

Rule Every value increments exactly one matching bucket. Finish with the correct frequency for every key.

Count value 30 picks

Incoming values

312302

Which bucket matches key 3?

07 — Use it wisely

Where Counting Sort fits

Scores and ratings

Bounded integer scores such as 0–100 need only a small predictable bucket table.

Excellent fit

▦

Category IDs

Dense integer codes can be grouped or ordered without comparison-based sorting.

Strong fit

⇥

Radix Sort passes

Stable Counting Sort is commonly used to order one digit position at a time.

Core building block

Wide or non-integer keys

Sparse huge ranges, decimals, and arbitrary strings make direct bucket allocation impractical.

Use another strategy

Lesson progress

Finish this lesson with confidence

Use this private checklist to confirm what you learned. Progress stays only in this browser.

0 of 4 complete0%

Judge the key rangeI can explain when k makes Counting Sort efficient or wasteful.Trace counts and prefixesI followed frequencies as they became cumulative positions.Read an implementationI identified the offset, count, prefix, and placement phases in one language.Practice the mechanicsI completed the knowledge check and frequency-table challenge.

Complete every checklist item to finish the lesson.