Medium

# 114. Counting Sort Algorithm

Counting Sort is a non-comparative 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:

1. 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.
2. Cumulative Counts:

• After counting the occurrences, Counting Sort updates the `Count` array so that each index `i` holds the cumulative count of elements less than or equal to `i`.
• This step ensures that each index in the `Count` array reflects the correct position for each element in the sorted output.
3. 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 in `Count[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.
4. 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]
```