- **Counting Sort** is a non-comparison-based sorting algorithm that counts the occurrences of each distinct element in the input array and uses this count to place elements in the correct position in the sorted output.
-
Steps:
Find the range of the input (maximum and minimum values).
Create a count array where the index represents the element and the value at each index represents the frequency of that element.
Modify the count array by adding the count of previous elements to each index, which helps in determining the correct position of each element.
Build the output array using the modified count array.
Time Complexity:
Best Case, Average Case, Worst Case:O(n + k) where n is the number of elements and k is the range of the input.