Bucket sort is a non-comparative sort. The principle is to create some buckets, each of which corresponds to a data interval, and the data to be sorted is allocated to different buckets, and the buckets are internally sorted.

Since it is not a sort of sorting, using Bucket sort requires knowing the scope and distribution of the data in advance to determine the interval corresponding to the bucket.

- Also known as
**bin sort**. **Stable sorting :**Elements of the same key value, the relative position does not change after sorting.**Distributive sorting :**Sorting by analyzing key-value distributions without comparing them. Linear execution time is available in specific situations.**Expected distribution :**The data is evenly distributed .

Suppose you want to sort an array of $n $ elements whose values are scattered evenly within a known expected range , such as 1 to 100.

**Create buckets :**Create an array of $k $ buckets. Each bucket corresponds to a certain range of the expected range , such as the first bucket is placed 1 to 10, and the second is placed 11 to 20.**Scatter :**Put each element into the corresponding bucket according to this value.**Inner sort :**Sort all non-empty buckets.**Gather :**Visit all the buckets in sequence and put the elements in the bucket back into the original array.

`/// Bucket sort`

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

/// * `hasher` - Function hashing to map elements to correspoding buckets.

/// Ref: https://codereview.stackexchange.com/a/145124

pub fn bucket_sort<H, F, T>(arr: &mut [T], hasher: F)

where
H: Ord,
F: Fn(&T) -> H,
T: Ord + Clone,

{
// 1. Create buckets.
let mut buckets: Vec<Bucket<H, T>> = Vec::new();

// 2. Iterate all elements.
for value in arr.iter() {
// 2.1 Create hasher mapping to certain bucket.
let hash = hasher(&value);

// 2.2 Search if the bucket with same hash exists.
let value = value.clone();
match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
// If exists, push the value to the bucket.
Ok(index) => buckets[index].values.push(value),
// If none, create and new bucket and insert value in.
Err(index) => buckets.insert(index, Bucket::new(hash, value)),
}
}

// 3. Iterate all buckets and flatten their internal collections.
let ret = buckets
.into_iter()
.flat_map(|mut bucket| {
bucket.values.sort(); // We use built-in sorting here.
bucket.values
})
.collect::<Vec<T>>();

// 4. Clone back to original array.
arr.clone_from_slice(&ret);
}

/// Bucket to store elements.

struct Bucket<H, T> {
hash: H,
values: Vec<T>,
}

impl<H, T> Bucket<H, T> {
/// Create a new bucket and insert its first value.
///
/// * `hash` - Hash value generated by hasher param of `bucket_sort`.
/// * `value` - Value to be put in the bucket.
pub fn new(hash: H, value: T) -> Bucket<H, T> {
Bucket {
hash,
values: vec![value],
}
}
}

#[cfg(test)]

mod base {
use super::*;
fn bucket_sort_(arr: &mut [i32]) {
bucket_sort(arr, |int| int / 4);
}
base_cases!(bucket_sort_);
}

#[cfg(test)]

mod stability {
use super::*;
fn bucket_sort_(arr: &mut [(i32, i32)]) {
bucket_sort(arr, |t| t.0 / 4);
}
stability_cases!(bucket_sort_);
}