Counting Sort Algorithm

Counting Sort Algorithm is a sorting algorithm that works best when you have a small range of numbers to sort. Instead of comparing elements like in other sorting methods, it counts how many times each number appears and then puts them in order based on that count. This makes it really fast when the range of numbers is not too big compared to the total number of items to be sorted.

Working of counting Sort Algorithm

1. Determine the maximum element, denoted as "max," from the provided array.

2. Create an array of length "max+1" with all elements initialized to 0. This array serves the purpose of storing the count of each element present in the given array.

3. Assign the count of each element to their corresponding index in the count array.

4. Calculate the cumulative sum of the elements in the count array. This cumulative sum assists in correctly positioning the elements in the sorted array.

5. Determine the index of each element from the original array in the count array, yielding the cumulative count. Place each element at the calculated index position in the sorted array, as illustrated in the figure below.

6. Once each element is correctly positioned, decrement its count by one in the count array.

Implementation of counting sort Algorithm

Counting sort in Java

Output:

Counting sort in C/C++

Output:

Counting sort in Python

Output:

Complexity Analysis of Counting Sort Algorithm

Time Complexity of Counting Sort Algorithm

The time complexity of the algorithm is O(N+M), where N denotes the size of the input array and M is the size of the count array. This holds true for worst-case, average-case, and best-case scenarios.

Space Complexity of Counting Sort Algorithm

The Space Complexity is O(N+M), accounting for the space used by the output array and the count array.

Applications of Counting Sort Algorithm

1. Counting sort Algorithm is employed for sorting arrays containing smaller integers with numerous repetitions.
2. It's chosen when achieving linear time complexity is crucial for efficient sorting operations.
3. Its effectiveness lies in efficiently handling scenarios where elements have limited range and frequent repetitions.

Advantage of Counting Sort Algorithm

1. Counting sort outperforms comparison-based sorting algorithms, like merge sort and quicksort, for inputs with a range comparable to the input size.
2. It offers simplicity in implementation, making it straightforward to code.
3. Counting sort maintains stability, preserving the original order of elements with equal values in the sorted output.

Disadvantage of Counting Sort Algorithm

1. Counting sort is incompatible with decimal values, limiting its applicability in sorting operations involving non-integer data.
2. Its efficiency diminishes significantly when sorting a large range of values, rendering it inefficient for such scenarios.
3. As a non-in-place sorting algorithm, counting sort necessitates additional space to store auxiliary data, impacting its memory usage compared to in-place algorithms.