Counting Sort
Counting Sort is an integer sorting algorithm that works by counting the occurrences of each element, then using that information to determine their positions in the output sequence. It's efficient when the range of potential items is not significantly greater than the number of items.
Steps:
- Count occurrences of each element in the input array
- Calculate the position of each element in the output array
- Build the output array based on these positions
Time Complexity
Best: O(n+k)
Average: O(n+k)
Worst: O(n+k)
Space Complexity
O(n+k)
Array length:
7
Speed: