Counting Sort Algorithm in DSA Rust

Mental Model

Counting sort counts how many times each number appears, then uses these counts to place numbers in order without comparing them.

Analogy: Imagine sorting colored balls by putting them into labeled boxes for each color, then taking them out in order to get a sorted line.

Unsorted array:
[4, 2, 2, 8, 3, 3, 1]

Count array (index = number):
[0, 1, 2, 2, 1, 0, 0, 0, 1]

Sorted array:
[1, 2, 2, 3, 3, 4, 8]

Dry Run Walkthrough

Input: array: [4, 2, 2, 8, 3, 3, 1]

Goal: Sort the array in ascending order using counting sort

Step 1: Find the maximum value to know count array size

Input array: [4, 2, 2, 8, 3, 3, 1]
Max value: 8

Why: We need to know how big the count array should be to cover all numbers

Step 2: Create count array with zeros for each number from 0 to max

Count array: [0, 0, 0, 0, 0, 0, 0, 0, 0]

Why: This array will hold how many times each number appears

Step 3: Count each number in input array and update count array

Count array after counting:
[0, 1, 2, 2, 1, 0, 0, 0, 1]

Why: Counting how many times each number appears helps us place them in order

Step 4: Modify count array to hold cumulative counts

Cumulative count array:
[0, 1, 3, 5, 6, 6, 6, 6, 7]

Why: Cumulative counts tell the position of each number in the sorted array

Step 5: Place each element from input array into output array using count array

Output array being filled step by step:
[_, _, _, _, _, _, _]
After placing 1: [1, _, _, _, _, _, _]
After placing 3s: [1, _, _, 3, 3, _, _]
After placing 2s: [1, 2, 2, 3, 3, _, _]
After placing 4: [1, 2, 2, 3, 3, 4, _]
After placing 8: [1, 2, 2, 3, 3, 4, 8]

Why: Using counts, we put each number in the right place to get a sorted array

Result:

Sorted array: [1, 2, 2, 3, 3, 4, 8]

Annotated Code

DSA Rust

fn counting_sort(arr: &[usize]) -> Vec<usize> {
    if arr.is_empty() {
        return vec![];
    }
    // Find max value to size count array
    let max_val = *arr.iter().max().unwrap();
    // Create count array initialized to 0
    let mut count = vec![0; max_val + 1];
    // Count occurrences
    for &num in arr {
        count[num] += 1;
    }
    // Cumulative count to get positions
    for i in 1..=max_val {
        count[i] += count[i - 1];
    }
    // Output array
    let mut output = vec![0; arr.len()];
    // Place elements in output using count
    for &num in arr.iter().rev() {
        count[num] -= 1; // decrement count for position
        output[count[num]] = num; // place number
    }
    output
}

fn main() {
    let arr = vec![4, 2, 2, 8, 3, 3, 1];
    let sorted = counting_sort(&arr);
    // Print sorted array
    for num in sorted {
        print!("{} ", num);
    }
    println!();
}

let max_val = *arr.iter().max().unwrap();

Find maximum value to size count array

for &num in arr { count[num] += 1; }

Count how many times each number appears

for i in 1..=max_val { count[i] += count[i - 1]; }

Convert counts to cumulative counts for positions

for &num in arr.iter().rev() { count[num] -= 1; output[count[num]] = num; }

Place each number in output array in correct position

Output

1 2 2 3 3 4 8 

Complexity Analysis

Time: O(n + k) because we count all n elements and create a count array of size k (max value)

Space: O(n + k) because we use output array of size n and count array of size k

vs Alternative: Compared to comparison sorts (O(n log n)), counting sort is faster when k (max value) is not much larger than n

Edge Cases

empty array

Returns empty array immediately

DSA Rust

if arr.is_empty() { return vec![]; }

array with one element

Returns array with that single element

DSA Rust

general logic works without special case

array with all elements the same

Count array counts correctly and output is same repeated element

DSA Rust

count[num] += 1;

When to Use This Pattern

When you need to sort integers quickly and know the range is small, use counting sort because it sorts without comparing elements.

Common Mistakes

Mistake: Not using cumulative counts to find correct positions
Fix: Add cumulative sum step to count array before placing elements

Mistake: Placing elements in output array in forward order causing overwrite
Fix: Traverse input array in reverse when placing elements to maintain stability

Summary

Counting sort sorts numbers by counting their occurrences and placing them using these counts.

Use it when sorting integers with a known small range for fast and stable sorting.

The key insight is using a count array to find exact positions without comparing elements.

Practice

1. What is the main idea behind the Counting Sort Algorithm?

easy

A. Compare each element with every other element to sort

B. Count the occurrences of each element and use counts to place elements in order

C. Divide the array into halves and sort recursively

D. Swap adjacent elements if they are in wrong order repeatedly

Solution

1. Step 1: Understand Counting Sort principle

   Counting sort counts how many times each value appears in the input.

2. Step 2: Use counts to place elements

   These counts help place elements directly in the sorted output without comparisons.

3. Final Answer:

   Count the occurrences of each element and use counts to place elements in order -> Option B

4. Quick Check:

   Counting sort = Counting occurrences and placing [OK]

Hint: Counting sort uses counts, not comparisons, to sort [OK]

Common Mistakes:

• Thinking counting sort compares elements
• Confusing counting sort with quicksort or mergesort
• Assuming counting sort works on all data types

2. Which of the following is the correct Rust syntax to create a vector of zeros with length 5 for counting sort?

easy

A. let counts = vec![0; 5];

B. let counts = vec(0, 5);

C. let counts = [0; 5];

D. let counts = vec::new(5, 0);

Solution

1. Step 1: Recall Rust vector initialization

   In Rust, vec![value; size] creates a vector with repeated values.

2. Step 2: Match syntax to create vector of zeros

   vec![0; 5] creates a vector with five zeros, perfect for counting sort.

3. Final Answer:

   let counts = vec![0; 5]; -> Option A

4. Quick Check:

   vec![0; 5] creates vector of 5 zeros [OK]

Hint: Use vec![value; size] to create repeated elements vector [OK]

Common Mistakes:

• Using parentheses instead of square brackets for vec!
• Confusing array syntax with vector syntax
• Trying to use vec::new with parameters

3. What will be the output of the following Rust code snippet implementing counting sort on array [4, 2, 2, 8, 3, 3, 1]?

fn counting_sort(arr: &[usize]) -> Vec<usize> {
    let max = *arr.iter().max().unwrap();
    let mut counts = vec![0; max + 1];
    for &num in arr {
        counts[num] += 1;
    }
    let mut sorted = Vec::new();
    for (num, &count) in counts.iter().enumerate() {
        for _ in 0..count {
            sorted.push(num);
        }
    }
    sorted
}

fn main() {
    let arr = [4, 2, 2, 8, 3, 3, 1];
    let sorted = counting_sort(&arr);
    println!("{:?}", sorted);
}

medium

A. [0, 1, 2, 3, 4, 8]

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

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

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

Solution

1. Step 1: Count occurrences of each number

   Input array: [4, 2, 2, 8, 3, 3, 1]. Counts: 1->1, 2->2, 3->2, 4->1, 8->1.

2. Step 2: Build sorted vector using counts

   Push each number count times in order: 1, 2, 2, 3, 3, 4, 8.

3. Final Answer:

   [1, 2, 2, 3, 3, 4, 8] -> Option D

4. Quick Check:

   Sorted array = [1, 2, 2, 3, 3, 4, 8] [OK]

Hint: Counting sort output is sorted array with repeated elements [OK]

Common Mistakes:

• Forgetting to repeat elements by their count
• Outputting original array instead of sorted
• Miscounting occurrences of elements

4. Identify the bug in this Rust counting sort code snippet and choose the fix:

fn counting_sort(arr: &[usize]) -> Vec<usize> {
    let max = arr.iter().max().unwrap();
    let mut counts = vec![0; *max];
    for &num in arr {
        counts[num] += 1;
    }
    let mut sorted = Vec::new();
    for (num, &count) in counts.iter().enumerate() {
        for _ in 0..count {
            sorted.push(num);
        }
    }
    sorted
}

medium

A. Change let max = arr.iter().max().unwrap(); to let max = *arr.iter().max().unwrap();

B. Change for &num in arr to for num in arr.iter()

C. Change vec![0; *max] to vec![0; *max + 1]

D. Change sorted.push(num) to sorted.push(count)

Solution

1. Step 1: Check vector size for counts

   Vector size is *max, but max element index is *max, so size must be *max + 1 to include max.

2. Step 2: Fix counts vector size

   Changing to vec![0; *max + 1] prevents out-of-bound errors when counting max element.

3. Final Answer:

   Change vec![0; *max] to vec![0; *max + 1] -> Option C

4. Quick Check:

   Counts vector size = max + 1 [OK]

Hint: Counts vector must cover all indices up to max element [OK]

Common Mistakes:

• Not adding +1 to vector size for max element
• Dereferencing max incorrectly
• Pushing count instead of element in sorted vector

5. You want to sort an array of integers that includes negative numbers using counting sort in Rust. Which approach correctly adapts counting sort for this case?

hard

A. Shift all numbers by adding the absolute value of the minimum negative number before counting

B. Use the original counting sort without changes; it works with negatives

C. Ignore negative numbers and sort only non-negative ones

D. Convert all numbers to positive by multiplying by -1 before sorting

Solution

1. Step 1: Understand counting sort limitation

   Counting sort requires non-negative indices for counts, so negatives cause index errors.

2. Step 2: Shift numbers to non-negative range

   Add absolute value of minimum negative number to all elements to shift them to zero or positive before counting.

3. Step 3: Sort and then shift back

   After sorting, subtract the shift to restore original values in sorted order.

4. Final Answer:

   Shift all numbers by adding the absolute value of the minimum negative number before counting -> Option A

5. Quick Check:

   Shift negatives to non-negative before counting sort [OK]

Hint: Shift negatives to zero or positive before counting sort [OK]

Common Mistakes:

• Trying to use counting sort directly on negatives
• Ignoring negative numbers in input
• Multiplying negatives by -1 changes order incorrectly