Introduction

Counting Sort Technique: Counting Sort is a non-comparison-based sorting algorithm that works by counting the frequency of elements in the input array. This frequency is then used to determine the position of each element in the sorted output array.
This technique gets its name because it relies on counting the occurrences of elements.

How can we sort an array?

• In Counting Sort, we create a count array to store the frequency of each distinct element.
• Using the count array, calculate the cumulative counts to determine the position of each element.
• Build the sorted output array by placing each element at its correct position based on cumulative counts.
• Finally, replace the original array with the sorted output array.

Important Observations

• Counting Sort is only applicable to integer arrays with a small range of values.
• It is a stable algorithm, meaning it preserves the relative order of equal elements.
• The algorithm is efficient for sorting large datasets when the range of values is limited.

Key Characteristics:

• Non-comparison-based sorting technique.
• Requires additional memory for the count array.
• Stable sorting algorithm.

Advantages:

• Efficient for arrays with a small range of values.
• Time complexity is \(O(n + k)\), where \(k\) is the range of values.
• Stable algorithm that preserves the order of equal elements.

Disadvantages:

• Not efficient for arrays with a large range of values.
• Requires additional memory for the count array.
• Only works for integers (not suitable for floating-point values or complex objects).

Time Complexity:

• Best Case: (O(n + k)).
• Average Case: (O(n + k)).
• Worst Case: (O(n + k)).