Bucket sort in Rust

Great work! One thing that stuck out to me was the use of extend; that shows that you've looked through the API docs to see what's available. Most of the time, people start out by just pushing all the elements from one vector to the other.

But I realized that passing a slice means that:

• either sorting must happen in place
• or elements must implement Copy

This analysis is correct, congratulations! In fact, this is something I like about Rust's type system. If I hand a method a &mut [T], then I know that it is very likely that it will be doing something in-place, presumably in an efficient manner.

Copy-ing is [...] probably inefficient on a large number of values

Types that implement Copy are those that be be semantically duplicated by copying bits but not executing any additional code. Generally, this is something that processors are good at. Types that are Clone, on the other hand, require some additional computation to occur when they are duplicated. These are the ones you want to be careful about duplicating needlessly. In general, I wouldn't worry about doing some copies.

Your point about Copy potentially being overly restrictive is quite valid though.

1. where clauses go on a separate line, and each additional restriction also goes on a separate line. This helps readability and understanding as those restrictions can dramatically change how a function should be called.

2. Use trailing commas just about everywhere in Rust.

3. I prefer to not add type restrictions on structs or methods that don't need them.

4. I prefer to not use into_iter when I can just pass the collection directly to something that accepts an IntoIterator.

5. Pick one of Vec::new or vec![] and be consistent with it.

6. Prefer for mut bucket in buckets instead of rebinding the variable just to add mutability.

7. Extend Bucket::new to take a value. You don't really need the ability to create an empty bucket.

8. The match arms can be one-lined.

9. flat_map and collect can be used to glom all of the intermediate vectors into one.

10. It's OK to compare a Vec<T> against an array of T. Use this in the tests to avoid needlessly allocating another vector.

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

impl<H, V> Bucket<H, V> {
    fn new(hash: H, value: V) -> Bucket<H, V> {
        Bucket {
            hash: hash,
            values: vec![value],
        }
    }
}

pub fn bucket_sort<T, F, H>(values: Vec<T>, hasher: F) -> Vec<T>
    where T: Ord,
          F: Fn(&T) -> H,
          H: Ord
{
    let mut buckets: Vec<Bucket<H, T>> = Vec::new();

    for value in values {
        let hash = hasher(&value);
        match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
            Ok(index) => buckets[index].values.push(value),
            Err(index) => buckets.insert(index, Bucket::new(hash, value)),
        }
    }

    buckets.into_iter().flat_map(|mut bucket| {
        bucket.values.sort();
        bucket.values
    }).collect()
}

#[test]
fn test_bucket_sort() {
    let values = vec![5, 10, 2, 99, 32, 1, 7, 9, 92, 135, 0, 54];
    let sorted_values = bucket_sort(values, |int| int / 10);
    assert_eq!(sorted_values,
               [0, 1, 2, 5, 7, 9, 10, 32, 54, 92, 99, 135]);
}