Skip to interview prep
Apexed

250. When can you sort in linear time? Explain counting, bucket and radix sort.

MediumSorting

Technical
Show model answer

Counting sort works when keys are integers in a small range [0, k): count occurrences, take prefix sums to get final positions, then place elements walking the input backwards to keep it stable. It costs O(n + k) time and space, so it is linear when k = O(n). Bucket sort distributes values (typically uniform reals in [0, 1)) into n buckets, sorts each small bucket and concatenates: expected O(n) under the uniform assumption, O(n²) worst if everything lands in one bucket.

Radix sort applies a stable sort (usually counting sort) digit by digit from the least significant digit. With d digits in base b it costs O(d(n + b)). The key insight is that the base is a choice: picking b close to n keeps each pass O(n), so integers that fit in a constant number of base-n digits sort in linear time.

When can you sort in linear time? Explain counting, bucket and radix sort. — Data structures & algorithms interview question — Apexed