250. When can you sort in linear time? Explain counting, bucket and radix sort.
MediumSorting
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.