Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the array, and stores these same elements in the auxiliary array. It was developed by Harold H. Seward in 1954.

### Complexity table of counting sort

Where n is the number of the element, and k is the range of the input.

### Algorithm of counting sort

Example 1: Suppose we have the following array, which we have to sort.

Step 1: Find the largest element in the given array.

Largest element is = 8   5 5 4 1 8 2 2 3

Step 2: Initialize a new array, and the size of the new array is (Largest + 1).

Step 3: Count each element in the given array, and stores the element at their respective index in the count array. For example: If 5 is assigned 2 times to the original array, then 2 will be stored at the 5th position in the count array. If 6 is assigned 0 times, then 0 will be stored at the 6th position in the count array.

Step 4: Make the cumulative sum of the elements of the count array. This helps to place the elements in the correct index of the sorted array.

Step 5:  This process will be implemented throughout the array.

Counting sort program in C language: