Explain the counting sort algorithm.

Counting sort is a linear sorting algorithm that works by counting the number of occurrences of each distinct element in an input array and then using this information to determine the position of each element in the sorted output array. It is particularly efficient when the range of input values is small compared to the size of the input array.

The counting sort algorithm can be divided into three main steps:

1. Counting: In this step, an auxiliary array called the count array is created. The count array is initialized with all zeros and has a size equal to the range of input values plus one. Each element in the input array is then iterated, and the count array is updated by incrementing the value at the corresponding index. This step essentially counts the number of occurrences of each element.

2. Accumulating: The count array is then modified by adding the value at each index with the value at the previous index. This step transforms the count array into a cumulative sum array, where each element represents the number of elements that are less than or equal to the corresponding index.

3. Sorting: Finally, a new output array is created with the same size as the input array. Starting from the last element of the input array, each element is placed in its correct position in the output array by using the count array to determine its index. After placing an element, the count value for that element is decremented by one. This process is repeated for all elements in the input array, resulting in a sorted output array.

Counting sort 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 input values. It is a stable sorting algorithm, meaning that elements with equal values appear in the same order in the sorted output as they do in the input.

However, counting sort has some limitations. It requires additional memory space for the count array, which can be a concern when the range of input values is large. Additionally, it can only be used for sorting non-negative integers or elements that can be mapped to non-negative integers.