How does the counting sort algorithm work?

Counting sort is a linear time sorting algorithm that works by counting the number of 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.

The algorithm works in three main steps:

1. Counting: First, the algorithm creates a count array of size k, where k is the range of the input elements. Each index of the count array represents a distinct element from the input array, and the value at each index represents the number of occurrences of that element in the input array. The count array is initialized with all zeros.

2. Accumulating: Next, the algorithm modifies the count array by calculating the cumulative sum of the counts. This step helps determine the correct position of each element in the sorted output array. Each value in the count array is updated by adding the value at the previous index.

3. Sorting: Finally, the algorithm iterates through the input array in reverse order. For each element, it looks up its count in the count array, which gives the correct position of the element in the sorted output array. After placing the element in its correct position, the count for that element is decremented by one to handle duplicate elements correctly.

The counting sort algorithm has a time complexity of O(n + k), where n is the number of elements in the input array and k is the range of the input elements. It is efficient when the range of input elements is small compared to the number of elements to be sorted. However, it requires additional memory space for the count array, making it less suitable for large ranges of input elements.