Overview
Counting Sort is a non-comparison-based sorting algorithm. It works by counting the number of occurrences of each distinct element
in the input, and then using this information to place each element in its correct position in the sorted array.
Time Complexity:
Best case: O(n + k) - Where 'n' is the number of elements and 'k' is the range of the input.
Average case: O(n + k) - It is unaffected by the initial order of elements.
Worst case: O(n + k) - The algorithm performs the same regardless of the input distribution.
Space Complexity: O(n + k) - Extra space is required to store the count array and the output array.
Counting Sort is efficient for sorting integers or objects with integer keys, and it is often used when the range of input values
is not significantly larger than the number of elements to be sorted.
let max = findMax(list)let count = new Array(max + 1).fill(0)for i = 0 to length(list) - 1 count[list[i]]++for i = 1 to max count[i] += count[i - 1]for i = length(list) - 1 to 0 output[count[list[i]] - 1] = list[i] count[list[i]]--for i = 0 to length(output) - 1 list[i] = output[i]
SHORT EXPLANATION------------------1. Find the maximum value in the list to determine the range.2. Create a count array to store the frequency of each element.3. Modify the count array such that each element at index i holds the sum of the counts up to i.4. Place the elements in the output array by using the count array to determine their positions.5. Copy the sorted elements back into the original list.