Beginner LevelData Structures & Algorithms
What are Counting Sort and Radix Sort and when do they beat O(N log N)?
ā Interview Prompt: Explain Counting Sort (O(N+K)) and Radix Sort (O(N*d)), when they outperform comparison-based sorts, and their limitations.
Counting Sort: $O(N + K)$ where $K$ = range of values
ā¢
Count frequency of each value ā compute cumulative counts ā place elements.
ā¢
Constraint: Only works with non-negative integer keys in a bounded range $[0, K]$.
ā¢
Ideal when $K = O(N)$ (e.g., sorting ages 0ā120, exam scores 0ā100).
Radix Sort: $O(N \times d)$ where $d$ = number of digits
ā¢
Sort digit by digit from least significant to most significant using a stable sub-sort (Counting Sort).
ā¢
Works on integers or fixed-length strings.
ā¢
Beats $O(N \log N)$ when $d \ll \log N$ and $K = O(N)$.
Code Implementation Example
typescript
// Counting Sort ā O(N + K)
function countingSort(arr: number[], maxVal: number): number[] {
const count = new Array(maxVal + 1).fill(0);
for (const n of arr) count[n]++;
const sorted: number[] = [];
for (let i = 0; i <= maxVal; i++) {
while (count[i]-- > 0) sorted.push(i);
}
return sorted;
}
console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
// [1, 2, 2, 3, 3, 4, 8]š”Counting Sort achieving O(N+K) by bypassing comparison operations.
šÆ Interview Key Takeaway
Counting/Radix Sort break the O(N log N) comparison barrier when input values are integers in a bounded range.
#DSA#Counting Sort#Radix Sort#Non-Comparison Sort#Beginner
Back to all Data Structures & Algorithms Questionsā