MergeSort in Rust

Question

I've just started learning Rust and put together this working MergeSort implementation. Wondering what I've overlooked and what I could improve.

I couldn't figure out a cleaner way to deal with the Option type returned by the iterator than just checking that values weren't None and then .unwrap()ing my results but I'd really appreciate any suggestions.

Included working test cases. Let me know if there's a case I missed.

pub fn merge_sort(mut input: Vec<usize>) -> Vec<usize> {
    let length = input.len();
    // Base case
    if length < 2 {
        return input;
    }

    let right = merge_sort(input.split_off(length / 2));
    let left = merge_sort(input);

    let mut left_iter = left.iter().peekable();
    let mut right_iter = right.iter().peekable();

    let mut merged = Vec::new();
    let mut i = 0;
    while i < length {
        if left_iter.peek() > right_iter.peek() && right_iter.peek() != None {
            merged.push(*(right_iter.next().unwrap()));
        } else if left_iter.peek() != None {
            merged.push(*(left_iter.next().unwrap()));
        }
        i += 1;
    }

    merged
}

#[cfg(test)]
mod tests {
    use merge_sort;

    #[test]
    fn it_works() {
        assert_eq!(merge_sort(vec![4, 3]), vec![3, 4]);
    }

    #[test]
    fn test_base_case() {
        assert_eq!(merge_sort(vec![3]), vec![3]);
    }

    #[test]
    fn totally_backwards() {
        assert_eq!(
            merge_sort(vec![100, 90, 50, 14, 9, 7, 3]),
            vec![3, 7, 9, 14, 50, 90, 100]
        );
    }

}

Answer 1

^{Disclaimer: I'm also new to Rust, but I have a background in C, C++ and Haskell. Take everything I say with a grain of salt.}

All of that looks reasonable, except for the while loop and the ownership. And there's a bug.

Bug on sorted vectors

Did you try your code on sorted sets?

#[test]
fn it_works_on_sorted() {
    assert_eq!(merge_sort(vec![1, 2, 3, 4]), vec![1, 2, 3, 4]);
}

Your code won't work. Instead, you'll end up with vec![1]. That's because

left_iter.peek() > right_iter.peek()

is false as soon as we run out of elements on the left hand side, since

None < Some(x)

is always true for all x. But in this case we won't add the elements from the right hand side! Instead, we look at our now empty left list:

if left_iter.peek() != None {
    // left_iter.peek() is None, not executed
    merged.push(*(left_iter.next().unwrap()));
}
// ALWAYS executed
i += 1;

Since i += 1 is always executed, we end up with i == length, although we never actually pushed the right-hand side. So i < length hides a bug. The next section shows how to get rid of that one:

While

Why do we have to keep track of the length of our vector? We have iterators at hand, so that shouldn't be necessary, right? When either of our iterators is at end, we fill our vector with the rest.

That's rather easy:

while let (Some(&x), Some(&y)) = (left_iter.peek(), right_iter.peek()) {
    if *x <= *y {
        merged.push(*(left_iter.next().unwrap()))
    } else {
        merged.push(*(right_iter.next().unwrap()))
    }
}

for x in left_iter {
    merged.push(*x)
}

for y in right_iter {
    merged.push(*y)
}

Vector::new() vs Vector::with_capacity

We already know that merged will have length elements, therefore we should use Vector::with_capacity instead:

let mut merged = Vec::with_capacity(length);

Ownership

merge_sort could take a slice instead of a vector. That way it's more general. The actual implementation is left as an exercise, but it's more or less the same:

/// Sorts a slice in-place with mergesort.
///
/// ```
/// let mut example = [1,4,2,5,3];
///
/// merge_sort_inplace(example)
/// assert_eq!(example, [1,2,3,4,5]);
/// ```
pub fn merge_sort_inplace(input: &mut [usize]) {
    let length = input.len();

    if length < 2 {
        return;
    }

    let (left, right) = input.split_at_mut(length / 2);

    merge_sort_inplace(left);
    merge_sort_inplace(right);

    // ... similar to your variant
}

Note that the name is slightly a misnomer, merge_sort_inplace will still need \$\mathcal \Theta(n)\$ additional memory unless you pull some tricks.

We can even re-use that variant if you still want to take ownership of the vector:

fn merge_sort(mut input: Vec<usize>) -> Vec<usize> {
    merge_sort_inplace(&mut input);
    input
}

Answer 2

The one obvious thing I see is that you are consuming the input. I'd suggest you try using slices instead, so that you don't consume the inputs and you don't have to spend time and memory splitting the vector.