Counting sort is a special integer sorting method that is considered a special case of Bucket sort . The principle is to count the number of occurrences of each key value within a known integer range and save it with an additional array (Count array). Finally, the element value of Count array is used as the new index of the sorted data.

- Non-in-place sorting: extra costing, non-fixed space to sort.
- Stable sorting: Elements of the same key value, the relative position does not change after sorting.
- Integer sort: The integer is used as the sorted key value.
- Distributive sorting: Sorting by analyzing key-value distributions without comparing them. Linear execution time is available in specific situations.
- Line type execution time: When the input data amount n is close to the difference between the upper and lower bounds of the known range, the execution time is close to the line type ( O(n) )
- Expected distribution: The expected input data is an integer (eg, 0 to k) that falls within a known range.
- Scope: Only applicable to small range integers (large space requirements).

**Count occurrence :**Calculates the number of occurrences of each key.**Prefix sum as start index :**Calculates the prefix and (Prefix sum) as the start index of the element.**Copy output :**Use the prefix and the second step to traverse the input data to obtain the index after the element is sorted.

`/// Counting sort`

/// * `arr` - Collection of value to be sorted in place.

/// * `min` - Lower bound of the integer range.

/// * `max` - Upper bound of the integer range.

/// * `key` - Function extracting key witn the integer range from elements.

pub fn counting_sort<F, T>(arr: &mut [T], min: usize, max: usize, key: F)

where
F: Fn(&T) -> usize,
T: Clone,

{
let mut prefix_sums = {
// 1. Initialize the count array with default value 0.
let len = max - min;
let mut count_arr = Vec::with_capacity(len);
count_arr.resize(len, 0);

// 2. Scan elements to collect counts.
for value in arr.iter() {
count_arr[key(value)] += 1;
}

// 3. Calculate prefix sum.
count_arr
.into_iter()
.scan(0, |state, x| {
*state += x;
Some(*state - x)
})
.collect::<Vec<usize>>()
};

// 4. Use prefix sum as index position of output element.
for value in arr.to_vec().iter() {
let index = key(value);
arr[prefix_sums[index]] = value.clone();
prefix_sums[index] += 1;
}
}

#[cfg(test)]

mod base {
use super::*;
fn counting_sort_(arr: &mut [i32]) {
counting_sort(arr, 1, 10, |int| *int as usize);
}
base_cases!(counting_sort_);
}

#[cfg(test)]

mod stability {
use super::*;
fn counting_sort_(arr: &mut [(i32, i32)]) {
counting_sort(arr, 1, 10, |t| t.0 as usize);
}
stability_cases!(counting_sort_);
}