Sorting Algorithms Questions Medium
The time complexity of the counting sort algorithm is O(n + k), where n is the number of elements to be sorted and k is the range of the input values.
Counting sort is a non-comparison based sorting algorithm that works by counting the occurrences of each distinct element in the input array and then using this information to determine the correct position of each element in the sorted output array. It is efficient when the range of input values is small compared to the number of elements to be sorted.
The algorithm first creates a count array of size k, where k is the maximum value in the input array. It then iterates through the input array, incrementing the count of each element in the count array. After that, it modifies the count array by adding the previous count to the current count, which gives the position of each element in the sorted output array.
Finally, it iterates through the input array again and places each element in its correct position in the output array based on the count array. This process takes linear time, as it only requires iterating through the input array twice.
Therefore, the time complexity of counting sort is O(n + k), where n is the number of elements to be sorted and k is the range of the input values.