Counting Sort

Algorithms

Counting sort is a non-comparison-based sorting algorithm that sorts elements by counting the number of occurrences of each unique element in the array.

Algorithm

The algorithm works by:

Counting the frequency of each element
Using these counts to determine the position of each element in the sorted array

Time Complexity

Counting sort has a time complexity of $O (n + k)$ , where $n$ is the number of elements and $k$ is the range of input values.

Implementation

def counting_sort(arr):
    if len(arr) == 0:
        return arr

    # Find the maximum and minimum values in the array
    max_val = max(arr)
    min_val = min(arr)
    
    # Initialize the count array with zeros
    count_range = max_val - min_val + 1
    count = [0] * count_range
    
    # Count the occurrences of each element
    for num in arr:
        count[num - min_val] += 1
    
    # Build the sorted array
    sorted_arr = []
    for i in range(count_range):
        sorted_arr.extend([i + min_val] * count[i])
    
    return sorted_arr

# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = counting_sort(arr)
print("Sorted array:", sorted_arr)