codaBack to Academy
sorting
Counting Sort
Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each distinct element and uses arithmetic to determine their positions in the output array. It achieves linear time complexity when the range of input values (k) is not significantly larger than the number of elements (n), making it extremely fast for integer data within a known range.
Use Cases
- •Sorting integers within a known, limited range
- •When linear time performance is required and data range is small
- •As a subroutine in radix sort for sorting by individual digits
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(n + k) | O(n + k) | O(n + k) |
| Space | O(n + k) | ||
Visualization
64
34
25
12
22
11
90
Implementation
Output
Click "Run Code" to see output...