Function counting_sort

pub fn counting_sort(arr: &mut [i32])

Sorts a slice using the Counting Sort algorithm.

Counting sort works by counting the occurrences of each element and then reconstructing the sorted array based on the counts.

Parameters

• arr: A mutable reference to the slice of integers to be sorted.

Time Complexity

• Best: O(n + k)
• Worst: O(n + k)
• Average: O(n + k)

Space Complexity

• O(k) (requires extra space for the count array)

Examples

use dsa::algorithms::sorting::counting_sort;

let mut arr = [5, 3, 8, 4, 2];
counting_sort(&mut arr);
assert_eq!(arr, [2, 3, 4, 5, 8]);