Counting Sort

---

Counting Sort is a non-comparison-based sorting algorithm that works by counting the number of occurrences of each distinct element in the input list. It is particularly efficient when the range of input values (the difference between the smallest and largest element) is not large relative to the number of elements in the list. Counting Sort runs in linear time O(n + k), where n is the number of elements in the input array and k is the range of the input (the difference between the maximum and minimum values).

---

What is Counting Sort?

Counting Sort is a sorting algorithm that uses an auxiliary array (or count array) to store the frequency of each element in the input list. The key idea behind Counting Sort is that it avoids the comparison of elements and instead directly determines the position of each element in the final sorted array by counting how many elements are less than or equal to it.

Key Properties of Counting Sort:

• Non-comparison-based: Unlike comparison-based algorithms like QuickSort or Merge Sort, Counting Sort doesn’t compare elements directly.
• Stable: Counting Sort is stable, meaning that elements with the same value retain their relative order.
• Efficient for Small Range: It is very efficient when the range of the input values (the difference between the maximum and minimum values) is small.
• Limited Applicability: It only works for non-negative integers or discrete values, making it less general-purpose than other sorting algorithms.

---

How Does Counting Sort Work?

The algorithm works in the following steps:

1. Determine the Range: Identify the range of the input elements (the minimum and maximum values).
2. Create the Count Array: Create an array to count the occurrences of each distinct element in the input list.
3. Accumulate Counts: Modify the count array by accumulating the count of each element up to the current index.
4. Place Elements in Sorted Order: Use the count array to place elements in the final sorted array based on their accumulated counts.

Steps of Counting Sort:

1. Count the Elements: For each element in the input array, count how many times it appears.
2. Compute Cumulative Count: Compute the cumulative sum of counts, which represents the position of each element in the sorted order.
3. Build the Sorted Array: Iterate through the input array in reverse order, placing each element in its correct position in the output array based on the cumulative count array.

---

Counting Sort: Python Code Implementation

Here is an implementation of Counting Sort in Python:

def counting_sort(arr):
    # Find the maximum value in the array to determine the range
    max_val = max(arr)
    min_val = min(arr)
    
    # Create a count array to store the frequency of each element
    count_array = [0] * (max_val - min_val + 1)
    
    # Count the occurrences of each element
    for num in arr:
        count_array[num - min_val] += 1
    
    # Rebuild the sorted array
    sorted_arr = []
    for i in range(len(count_array)):
        sorted_arr.extend([i + min_val] * count_array[i])
    
    return sorted_arr

# Example usage:
arr = [38, 27, 43, 3, 9, 82, 10]
print("Unsorted Array:", arr)
sorted_arr = counting_sort(arr)
print("Sorted Array:", sorted_arr)

Output:

Unsorted Array: [38, 27, 43, 3, 9, 82, 10]
Sorted Array: [3, 9, 10, 27, 38, 43, 82]

Explanation of Code:

• Count Array: A count array is created where the index represents the range of values, and the value at each index represents the frequency of that number in the input array.
• Rebuild Sorted Array: The sorted array is reconstructed by iterating through the count array and adding each element to the sorted result based on its frequency.

---

Time and Space Complexity of Counting Sort

Time Complexity:

• Best Case: $O(n+k)$ – Counting Sort always runs in linear time, where n is the number of elements in the input array, and k is the range of the input (the difference between the maximum and minimum values).
• Worst Case: $O(n+k)$ – Even in the worst case, the time complexity remains linear with respect to the number of elements and the range.
• Space Complexity: $O(k)$ – Counting Sort requires extra space for the count array, which has a size proportional to the range of the input values.

Overall Complexity: The algorithm is highly efficient when k is much smaller than n.

---

Advantages of Counting Sort

1. Linear Time Complexity: Counting Sort runs in linear time $O(n+k)$, which can be faster than comparison-based algorithms like QuickSort or Merge Sort, especially for small ranges of input data.
2. Stable Sort: It preserves the relative order of elements with equal values, making it stable.
3. Efficient for Certain Types of Data: When dealing with a small range of integers, Counting Sort is highly efficient.

---

Disadvantages of Counting Sort

1. Limited Applicability: Counting Sort only works for integer values or other discrete values, and is not suitable for sorting floating-point numbers, strings, or complex data structures.
2. Space Complexity: The space complexity of $O(k)$ can be prohibitive if the range of input values is large. This makes Counting Sort impractical for sorting large datasets with wide ranges of values.
3. Not a Comparison Sort: Although Counting Sort is not comparison-based, its efficiency depends on the range of input data. It can perform poorly if the range is too large.

---

When to Use Counting Sort?

1. Small Range of Values: When the range of input values (the difference between the maximum and minimum values) is small relative to the number of elements, Counting Sort performs very well.
2. Integer Sorting: Counting Sort is ideal for sorting integer data or other discrete values such as non-negative integers.
3. Stable Sorting Needed: When stability (preserving the relative order of equal elements) is required, Counting Sort is a good choice.

---

---