Counting Sort

Counting sort is a non-comparison sorting algorithm that works by counting the number of occurrences of each distinct value. Instead of comparing elements directly, it uses the values themselves as indices into a frequency array. This allows counting sort to achieve linear time complexity under specific constraints.

Counting sort is extremely efficient when the range of input values is small relative to the number of elements.

Example Walk-through

Consider the following array of non-negative integers:

[4, 2, 2, 8, 3, 3, 1]

Step 1 - Find the maximum value

The maximum element is 8. This determines the size of the counting array.

Step 2 - Count occurrences

Create a count array of size max + 1:

Index:  0 1 2 3 4 5 6 7 8
Count:  0 1 2 2 1 0 0 0 1

Each index represents a value from the original array, and the count represents how many times it appears.

Step 3 - Reconstruct the sorted array

Iterate through the count array and rebuild the original array by placing each value according to its frequency:

[1, 2, 2, 3, 3, 4, 8]

Unlike comparison-based sorts, counting sort does not swap elements - it reconstructs the sorted list directly from the frequency counts.

Rust Implementation

This implementation assumes non-negative integers and sorts the array in-place using an auxiliary counting array.

pub fn counting_sort(arr: &mut [usize]) {
    if arr.is_empty() {
        return;
    }

    // Find the maximum value
    let max_value = *arr.iter().max().unwrap();

    // Create counting array
    let mut count = vec![0; max_value + 1];

    // Count occurrences
    for &value in arr.iter() {
        count[value] += 1;
    }

    // Reconstruct the sorted array
    let mut index = 0;
    for value in 0..=max_value {
        for _ in 0..count[value] {
            arr[index] = value;
            index += 1;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_sorts() {
        let mut input = vec![4, 2, 2, 8, 3, 3, 1];
        counting_sort(&mut input);
        assert_eq!(input, vec![1, 2, 2, 3, 3, 4, 8]);
    }
}

Example Usage

fn main() {
    let mut values = vec![3, 6, 4, 1, 3, 4, 1, 4];
    counting_sort(&mut values);
    println!("{:?}", values); // [1, 1, 3, 3, 4, 4, 4, 6]
}

Time and Space Complexity

Counting sort’s performance depends on both the number of elements (n) and the range of input values (k).

Space Complexity

When to Use Counting Sort

Counting sort is ideal when:

• The input values are non-negative integers
• The value range (k) is small
• Stability or raw speed is more important than memory usage

It is not suitable when the value range is large or unbounded.

Playground Links

Rust - Counting Sort