Counting Sort is a noncomparative sorting algorithm that sorts integers in linear time, given a fixed range of integer values. Unlike comparisonbased algorithms such as Quick Sort or Merge Sort, Counting Sort leverages the distribution of values within the input array to achieve its efficiency. This makes it particularly useful for sorting arrays with a limited range of integer values.
Approach
Counting Sort works by counting the occurrences of each unique value in the input array and then using this information to place each value in its correct position in the sorted array. The approach can be broken down into the following steps:

Initialization:
 First, the algorithm identifies the maximum value (
max_val
) in the array. This value determines the size of the counting array,count
, which tracks the frequency of each value in the input array.
 First, the algorithm identifies the maximum value (

Counting Occurrences:
 The algorithm then iterates over the input array and increments the corresponding index in the
count
array for each value encountered. Thecount
array essentially records the number of times each value appears in the input array.
 The algorithm then iterates over the input array and increments the corresponding index in the

Reconstructing the Sorted Array:
 Finally, the algorithm iterates through the
count
array and reconstructs the sorted array. For each value in thecount
array with a nonzero count, the value is placed in the output array in the correct order based on its frequency.
 Finally, the algorithm iterates through the
Code Explanation
void countingSort(vector<int>& arr) {
if (arr.empty()) return; // Edge case: If the array is empty, there's nothing to sort
// Find the maximum value in the array
int max_val = *max_element(arr.begin(), arr.end());
// Create a count array to store the frequency of each value
vector<int> count(max_val + 1, 0);
// Count the occurrences of each value in the array
for (int num : arr) {
count[num]++;
}
// Reconstruct the sorted array using the count array
int sorted_index = 0;
for (int i = 0; i <= max_val; ++i) {
while (count[i] > 0) {
arr[sorted_index++] = i;
count[i];
}
}
}
How It Works

Counting Occurrences: The core idea of Counting Sort is to count the number of occurrences of each integer in the input array. This is done using the
count
array, where the index represents the integer value, and the value at each index represents the frequency of that integer in the input array. 
Reconstructing the Array: After counting the occurrences, the algorithm reconstructs the sorted array by iterating through the
count
array. For each indexi
in thecount
array, ifcount[i]
is greater than zero,i
is placed into the sorted array as many times ascount[i]
indicates.
Complexity Analysis

Time Complexity: The time complexity of Counting Sort is O(n + k), where
n
is the number of elements in the input array, andk
is the range of the input (i.e., the difference between the maximum and minimum values). This makes Counting Sort highly efficient for cases wherek
is not significantly larger thann
. 
Space Complexity: The space complexity of Counting Sort is O(k), where
k
is the range of the input values. This space is used to store thecount
array. Additionally, the space for the output array is O(n), but since the sorting is done inplace in this implementation, the extra space required is mainly for thecount
array.