# What is Counting Sort

Counting sort is a sorting algorithm that works by counting the number of occurrences of each unique element in a list and using that information to sort the list. Here's how it works:

- Counting: First, we create a "count" array that stores the number of occurrences of each unique element in the input list. We iterate through the input list, and for each element we encounter, we increment the corresponding count in the count array.
- Accumulation: Next, we modify the count array so that each element stores the sum of the previous counts. This means that each element in the count array represents the number of elements that are less than or equal to the corresponding element in the input list.
- Sorting: Finally, we create a new output list and iterate through the input list again. For each element, we use the count array to determine its sorted position in the output list, and then we decrement the corresponding count in the count array. This process ensures that elements with the same value are sorted in the same order as they appeared in the input list.

## Who invented it?

Counting sort was first introduced by Harold Seward in 1954, but the algorithm was independently discovered by Ivan Munro and Vladimir Sukharev in the same year. Seward's paper "The Distribution Sort - A Technique for Correlating and Disseminating Data" described a variant of counting sort that was used to sort punched card data, while Munro and Sukharev's paper "Sorting and Searching" presented a more general version of the algorithm. The algorithm has since been refined and improved by many researchers, and is now widely used in various applications

## Pseudocode

```
countingSort(list, maxVal):
// Create a count array with length maxVal+1 and initialize each element to 0
count = new Array(maxVal+1)
for i = 0 to maxVal:
count[i] = 0
// Count the number of occurrences of each element in the list
for i = 0 to length(list)-1:
count[list[i]] = count[list[i]] + 1
// Modify the count array so that each element represents the sum of the previous counts
for i = 1 to maxVal:
count[i] = count[i] + count[i-1]
// Create a new output list and sort the elements based on their counts
output = new Array(length(list))
for i = length(list)-1 down to 0:
output[count[list[i]]-1] = list[i]
count[list[i]] = count[list[i]] - 1
// Return the sorted output list
return output
```

In this pseudocode, list is the input list to be sorted, and maxVal is the maximum value that can appear in the input list. The algorithm first creates a count array with length maxVal+1 and initializes each element to 0. It then counts the number of occurrences of each element in the input list by iterating through the list and incrementing the corresponding count in the count array. The count array is then modified so that each element represents the sum of the previous counts, and a new output list is created. The input list is then iterated through again, and each element is placed in its sorted position in the output list based on its count. Finally, the sorted output list is returned.

## Sample Code

```
// C++ code snippet
vector
``` countingSort(vector list, int maxVal) {
// Create a count array with length maxVal+1 and initialize each element to 0
vector count(maxVal+1, 0);
// Count the number of occurrences of each element in the list
for (int i = 0; i < list.size(); i++) {
count[list[i]]++;
}
// Modify the count array so that each element represents the sum of the previous counts
for (int i = 1; i <= maxVal; i++) {
count[i] += count[i-1];
}
// Create a new output list and sort the elements based on their counts
vector output(list.size());
for (int i = list.size()-1; i >= 0; i--) {
output[count[list[i]]-1] = list[i];
count[list[i]]--;
}
// Return the sorted output list
return output;
}
int main() {
vector list = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int maxVal = 9;
vector sortedList = countingSort(list, maxVal);
cout << "Sorted list: ";
for (int i = 0; i < sortedList.size(); i++) {
cout << sortedList[i] << " ";
}
cout << endl;
return 0;
}

```
# Python code snippet
def counting_sort(lst, max_val):
# Create a count array with length max_val+1 and initialize each element to 0
count = [0] * (max_val+1)
# Count the number of occurrences of each element in the list
for num in lst:
count[num] += 1
# Modify the count array so that each element represents the sum of the previous counts
for i in range(1, max_val+1):
count[i] += count[i-1]
# Create a new output list and sort the elements based on their counts
output = [0] * len(lst)
for i in range(len(lst)-1, -1, -1):
output[count[lst[i]]-1] = lst[i]
count[lst[i]] -= 1
# Return the sorted output list
return output
# Example usage:
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
max_val = 9
sorted_lst = counting_sort(lst, max_val)
print("Sorted list:", sorted_lst)
```

```
import java.util.Arrays;
public class CountingSort {
public static int[] countingSort(int[] arr, int maxVal) {
// Create a count array with length maxVal+1 and initialize each element to 0
int[] count = new int[maxVal+1];
// Count the number of occurrences of each element in the array
for (int num : arr) {
count[num]++;
}
// Modify the count array so that each element represents the sum of the previous counts
for (int i = 1; i <= maxVal; i++) {
count[i] += count[i-1];
}
// Create a new output array and sort the elements based on their counts
int[] output = new int[arr.length];
for (int i = arr.length-1; i >= 0; i--) {
output[count[arr[i]]-1] = arr[i];
count[arr[i]]--;
}
// Return the sorted output array
return output;
}
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int maxVal = 9;
int[] sortedArr = countingSort(arr, maxVal);
System.out.print("Sorted array: ");
System.out.println(Arrays.toString(sortedArr));
}
}
```

## Time and Space Complexity

- The time complexity of counting sort is O(n+k), where n is the number of elements to be sorted and k is the range of the input values. This makes counting sort very efficient when k is relatively small compared to n.
- The space complexity of counting sort is also O(n+k), since it requires creating a count array with length k+1 and an output array with length n.
- In practice, counting sort can be very fast and efficient for sorting large datasets when the range of input values is not too large. However, it may not be as efficient as other sorting algorithms (such as quicksort or merge sort) when the range of input values is very large.

## Advantages

- Counting sort is very fast and efficient when the range of input values is relatively small compared to the number of elements to be sorted (i.e., when k is much smaller than n).
- Counting sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the input array. This can be important in certain applications where the order of equal elements is significant.
- Counting sort is a non-comparison sorting algorithm, which means that it does not rely on comparing elements to each other to determine their order. This makes it faster than comparison-based sorting algorithms (such as quicksort or merge sort) in many cases.

## Disadvantages

- Counting sort requires a large amount of memory if the range of input values is very large (i.e., if k is close to n). This can make it impractical or even impossible to use in some cases.
- Counting sort is not suitable for sorting data that has a large number of duplicate values. In such cases, the count array can become very large and the algorithm can become less efficient.
- Counting sort is not an in-place sorting algorithm, which means that it requires additional memory to store the count array and the output array. This can be a disadvantage if memory usage is a concern.