Counting Sort Algorithm | Integer-based Linear Time Sorting Method

Description

Counting Sort is a non-comparison based sorting algorithm that works by counting the number of occurrences of each element in the array. It operates by creating an auxiliary array to store the frequencies of each element, and then using this information to place elements in their correct sorted positions.

History

Counting Sort emerged in the early days of computer science, during the 1950s, when researchers were exploring non-comparison based sorting methods. Unlike many other sorting algorithms that are named after their inventors, Counting Sort is named after its process of counting elements. The algorithm gained prominence as a subroutine in Radix Sort, where it's used to sort numbers digit by digit. Its ability to sort in linear time made it particularly valuable in specific applications where the range of input values is known and reasonably small compared to the number of items to be sorted. The algorithm has found widespread use in various applications, from sorting postal codes to computer graphics rendering pipelines where elements need to be sorted by depth (z-index).

How It Works

Count Frequencies:
- Create a count array of size k (range of input)
- Count occurrences of each element
Calculate Cumulative Count:
- Modify count array to store actual positions
- Each element shows final position of elements
Build Output Array:
- Place each element in its correct position
- Decrement count for each placement

Visualization

Speed:

Click Start to begin visualization

Implementation


def counting_sort(arr):
    # Find the range of input array
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1
    
    # Initialize count array and output array
    count = [0] * range_val
    output = [0] * len(arr)
    
    # Store count of each element
    for i in arr:
        count[i - min_val] += 1
    
    # Modify count array to store actual positions
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # Build output array
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    
    # Copy output array to input array
    for i in range(len(arr)):
        arr[i] = output[i]
    
    return arr


void countingSort(vector& arr) {
    // Find range of array elements
    int max_val = *max_element(arr.begin(), arr.end());
    int min_val = *min_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;
    
    // Create count array and output array
    vector count(range), output(arr.size());
    
    // Store count of each element
    for(int i = 0; i < arr.size(); i++)
        count[arr[i] - min_val]++;
        
    // Modify count array to store actual positions
    for(int i = 1; i < count.size(); i++)
        count[i] += count[i-1];
        
    // Build output array
    for(int i = arr.size()-1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }
    
    // Copy output array to input array
    for(int i = 0; i < arr.size(); i++)
        arr[i] = output[i];
}

// Example usage
int main() {
    vector arr = {64, 34, 25, 12, 22, 11, 90};
    cout << "Original array: ";
    for(int num : arr) cout << num << " ";
    
    countingSort(arr);
    
    cout << "\nSorted array: ";
    for(int num : arr) cout << num << " ";
    return 0;
}


public class CountingSort
{
    public static void Sort(int[] arr)
    {
        // Find range of array elements
        int maxVal = arr.Max();
        int minVal = arr.Min();
        int range = maxVal - minVal + 1;
        
        // Create count array and output array
        int[] count = new int[range];
        int[] output = new int[arr.Length];
        
        // Store count of each element
        for(int i = 0; i < arr.Length; i++)
            count[arr[i] - minVal]++;
            
        // Modify count array to store actual positions
        for(int i = 1; i < count.Length; i++)
            count[i] += count[i - 1];
            
        // Build output array
        for(int i = arr.Length - 1; i >= 0; i--)
        {
            output[count[arr[i] - minVal] - 1] = arr[i];
            count[arr[i] - minVal]--;
        }
        
        // Copy output array to input array
        for(int i = 0; i < arr.Length; i++)
            arr[i] = output[i];
    }
    
    // Example usage
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        
        Sort(arr);
        
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Applications

Sorting integers with known range
Sorting postal codes
Sorting strings (as part of radix sort)
Computer graphics (sorting by z-index)
DNA sequence analysis

Advantages and Disadvantages

Advantages

Linear time complexity O(n + k)
Stable sorting algorithm
Efficient for integers with known range
Good as a subroutine in radix sort

Disadvantages

Not in-place sorting
Requires extra space O(k)
Only works with discrete values
Not efficient when range k is much larger than n

Complexity Analysis

Case	Time Complexity	Description
Best Case	Ω(n + k)	Always performs same operations regardless of input arrangement
Average Case	Θ(n + k)	Requires two passes through array of size n and one through count array of size k
Worst Case	O(n + k)	Same as other cases due to non-comparative nature
Space Complexity	O(k)	Requires count array of size k and output array of size n

Notes:

n - Number of elements in the input array
k - Range of input (max - min + 1)
Linear time complexity when k = O(n)
Not efficient when k >> n (range much larger than array size)
Performance independent of input distribution

Quick Info

Counting Sort