Be the first user to complete this post

Add to List 
114. Counting Sort Algorithm
Counting Sort is a noncomparative integer sorting algorithm that works efficiently when the range of input values is relatively small compared to the number of elements to be sorted. It's often used when the input consists of integers within a known range, such as in cases where the input values are bounded by a constant or a small range of integers.
Implementation:

Counting Occurrences:
 Counting Sort begins by counting the occurrences of each distinct element in the input array. It creates an auxiliary array, usually called
Count
, to store these counts.  The
Count
the array has a size equal to the range of the input values plus one, as it will store the count of each integer from 0 to the maximum value present in the input array.
 Counting Sort begins by counting the occurrences of each distinct element in the input array. It creates an auxiliary array, usually called

Cumulative Counts:
 After counting the occurrences, Counting Sort updates the
Count
array so that each indexi
holds the cumulative count of elements less than or equal toi
.  This step ensures that each index in the
Count
array reflects the correct position for each element in the sorted output.
 After counting the occurrences, Counting Sort updates the

Building the Sorted Array:
 With the
Count
array prepared, Counting Sort traverses the input array in a forward or backward direction, depending on the sorting order needed.  For each element input
[i]
in the input array, Counting Sort finds its correct position in the output array using the count stored inCount[input[i]]
.  After placing an element in its correct position, Counting Sort decrements the count to indicate that this element has been accounted for in the sorted output.
 With the

Output:
 Once all elements have been placed in the correct positions in the output array, Counting Sort returns the sorted array.
Time complexity: O(n + k)
Space Complexity: O(n + k)
n
is the number of elements in the input array and k
is the range of the input values
Output:
Orginal Array [2, 1, 4, 5, 7, 1, 1, 8, 9, 10, 11, 14, 15, 3, 2, 4] Sorted Array : [0, 1, 1, 1, 2, 2, 3, 4, 4, 5, 7, 8, 9, 10, 11, 14, 15]