loading
loading
loading
Computer Science / Algorithms
Count occurrences of each value directly instead of comparing elements — O(n + k) time when the value range k is small and known.
Counting sort never compares two elements to each other — that's what makes it fundamentally different from every other sorting visualizer on this platform. Instead, it counts how many times each possible value occurs (the input row feeds a count histogram, one bucket per value), then walks the buckets in ascending order, writing each value out as many times as it was counted (the output row fills left to right). This only works because the demo's assumption makes it work: every value is a non-negative integer in a small, fixed, known range — 0 to 20 here — so a bucket can exist for every possible value up front. Given that assumption, the whole sort costs O(n + k): one pass to count (n) and one pass over the buckets to place (k), with no comparisons anywhere. Press Shuffle to generate a new random input in the same fixed range and watch the count-then-place process repeat.
Because counting sort genuinely never compares two elements — Bubble, Selection, Insertion, Quick, and Merge Sort all decide order by comparing pairs of values, but counting sort decides order by counting occurrences and reading buckets in order. Omitting the counter isn't an oversight; it's the whole point of this visualizer.
Counting sort needs one bucket for every possible value in the range, whether or not that value actually appears in the input — so the buckets array itself costs O(k) space and O(k) time to walk, regardless of n. If the range were huge (or unbounded, or the values weren't integers), the bucket array would be impractically large or impossible to build at all. This is a genuine precondition, not a simplification this demo happens to make — Bubble through Merge Sort have no such requirement.
Counting sort can be made stable, but it takes an extra step this visualizer skips for clarity: converting the counts into running totals (a prefix sum) and placing elements back-to-front using each element's original position, rather than this demo's simpler approach of just placing count[v] copies of each value in ascending order. Since this demo sorts plain numbers with no attached identity, there's nothing here to observe being reordered — but if you sorted objects by a key this way, without the prefix-sum step, their relative order would not be preserved.