Counting sort is an integer sorting algorithm used in computer science to collect objects according to keys that are small positive integers. It works by determining the positions of each key value in the output sequence by counting the number of objects with distinct key values and applying prefix sum to those counts.
Complexity Analysis of Counting Sort:
Time Complexity: O(N+M), where N and M are the size of inputArray[] and countArray[] respectively.
Worst-case: O(N+M).
Average-case: O(N+M).
Best-case: O(N+M).
Auxiliary Space: O(N+M), where N and M are the space taken by outputArray[] and countArray[] respectively.
#dsalgo #datastructures #dsa #countingsort #java