Count Sort is a sorting algorithm that sorts an array by counting how many times each unique element appears in the array. The count is stored in an auxiliary array, and sorting is carried out by mapping the count to an index in the auxiliary array.
This occurs when no sorting is necessary, implying that the array is already sorted. The best-case time complexity for counting sort is O(n + k).
This arises when the array elements are jumbled and do not appropriately get or descend. The average time complexity of a counting sort is O(n + k).
This occurs when array members must be sorted in reverse order. That is, assume you need to sort the array elements in ascending order but the elements are in descending order. The worst-case time complexity of a counting sort is O(n + k).
We utilize an extra array of size K, the array's largest element, to record the frequencies of all elements in the range [0, K]. Thus, the space complexity is strongly dependent on the value of K and is equal to O(K).