How does the counting sort algorithm function?

Counting sort is a sorting algorithm that sorts elements by counting the number of occurrences of each unique element in the array.

Counting sort is a non-comparison based sorting algorithm, which means it doesn't compare elements to sort them. Instead, it creates an auxiliary array (count array) to hold the count of each unique element in the input array. The size of the count array is equal to the maximum element in the input array. The algorithm then modifies the count array such that each element at each index stores the sum of previous counts. This modified count array indicates the position of each object in the output sequence.

The algorithm works in three steps. Firstly, it counts the number of times each number appears in the input array and stores this information in the count array. Secondly, it performs a prefix sum computation on the count array to get the starting index for each number in the output array. The prefix sum computation modifies the count array such that each element at each index stores the sum of previous counts. Finally, it iterates over the input array from the end, and for each element, it places it in the output array at the index specified by the count array, and then decreases the count by one.

Counting sort is efficient when the range of input data (k) is not significantly greater than the number of objects (n) to be sorted. It has a time complexity of O(n+k) and a space complexity of O(n+k), where n is the number of elements in the input array and k is the range of input data.

However, counting sort is not a comparison sort and is often used as a subroutine in other sorting algorithms like radix sort. It's also not suitable for sorting arrays that contain negative numbers or floating-point numbers. It's important to note that counting sort is a stable sort, which means that it maintains the relative order of equal elements in the sorted output.