Insertion sort in Rust

Question

Here is the code:

pub fn insertion_sort<T>(vec: &mut Vec<T>) where T: Ord + Copy {
    fn insert<U>(vec: &mut Vec<U>, pos: usize, value: U) where U: Ord + Copy {
        assert!(pos > 0);
        let mut pos: usize = pos - 1;
        loop {
            let value_at_pos = vec[pos]; 
            if value_at_pos <= value {
                break;
            }
            vec[pos + 1] = value_at_pos; 
            if pos == 0 {
                vec[pos] = value;
                return ();
            }
            pos -= 1;
        }
        vec[pos + 1] = value;
    }
    for i in 1..vec.len() {
        let value = vec[i];
        insert(vec, i, value);
    }
}

#[test]
fn test_insertion_sort() {
    let mut vec = vec![9, 8, 7, 11, 10]; 
    insertion_sort(&mut vec);
    let vec_res: Vec<_> = (7..12).collect();
    assert_eq!(vec, vec_res);
}

It's slightly more complex than in textbooks due to the fact negative integers are not allowed for indexing in Rust, not a huge problem though.

Answer 1

1. As you have already been made aware, you should not be using &mut Vec<T> unless you plan on adding or removing items from the Vec. Using &mut [T] better expresses the contract of the function and is more flexible, allowing you to also sort arrays and anything else that can be expressed as a slice.

2. where clauses go on a separate line. This allows them to be easily found, which is important considering how much they affect the behavior of the function.

3. There's no need to declare the type of pos. Type inference will take care of it.

4. There's no need to redeclare pos just to make it mutable and decrement it. Just make the variable binding in the function declaration mut.

5. There's no need to return the unit value (()). Just return will suffice.

6. slice::swap exists. In the broader world, so does mem::swap.

7. With the power of swap, you can remove the need for the Copy bound.

8. Quickcheck is an invaluable tool for problems like this. You can create a property that can be validated across a wide range of automatically generated input.

pub fn insertion_sort<T>(values: &mut [T])
    where T: Ord
{
    for i in 0..values.len() {
        for j in (0..i).rev() {
            if values[j] >= values[j + 1] {
                values.swap(j, j + 1);
            } else {
                break
            }
        }
    }
}

#[macro_use]
extern crate quickcheck;

#[test]
fn test_insertion_sort_empty() {
    let mut values: [i32; 0] = [];
    insertion_sort(&mut values);
    assert_eq!(values, [])
}

#[test]
fn test_insertion_sort_one() {
    let mut values = [1];
    insertion_sort(&mut values);
    assert_eq!(values, [1]);
}

#[test]
fn test_insertion_multi() {
    let mut values = [9, 8, 7, 11, 10];
    insertion_sort(&mut values);
    let values_expected: Vec<_> = (7..12).collect();
    assert_eq!(values_expected, values);
}

quickcheck! {
    fn test_insertion_everything(xs: Vec<i32>) -> bool {
        // Macro doesn't allow `mut` in the `fn` declaration :-(
        let mut xs = xs;

        let mut expected_sorted = xs.clone();
        expected_sorted.sort();

        insertion_sort(&mut xs);

        expected_sorted == xs
    }
}