Counting Sort — Frequency Factory

Count in buckets → prefix sums → stable output conveyor.

1) Setup

Input type

Max value (k)

Input size (n)

Speed

1.8×

Drop / Move duration

0.55s

Coach: Counting Sort does not compare elements. It counts how many of each value exists, then uses prefix sums to place each item in the right final position.

Blue drops into buckets • Purple turns counts into positions • Gold conveyor locks sorted output.

2) Counters

Reads

Writes

Bucket Adds

Output Built

Press Step. Watch elements fall into buckets, then the prefix-sum machine creates exact landing spots, then the output conveyor builds the sorted array stably.

3) Notes

Time: O(n + k)
Space: O(n + k)
Stable: Yes (when we place from right to left)

This lab shows the stability by keeping colored tags for equal values.