Is there a way to elegantly solve `move behind a mutable reference` without implementing the `Copy` trait?

Question

I'm trying to implement the merge function for my merge sort in Rust. The catch is that I'm trying to do it for a generic type T, which is only restrained by std::cmp::PartialOrd.

This is the code:

fn my_merge<T: std::cmp::PartialOrd>(a: &mut Vec<T>, mut b: &mut Vec<T>) -> Vec<T> {
    let mut res: Vec<T> = Vec::new();
    let mut a_iter = a.into_iter();  //  !!!
    let mut b_iter = b.into_iter();  //  !!!

    while let (Some(a_item), Some(b_iter)) = (a_iter.next(), b_iter.next()) {
        if a_item <= b_item {
            res.push(*a_item);  // !!!
        } else {
            res.push(*b_item);  // !!!
        }        
    }

    // ... Omitted code ...

    res
}

When looking at documentation, I discovered the into_iter() method, with which the next() method is supposed to yield T instead of &T. But it only does so if the iterator isn't constructed on a reference (since I'm passing a slice into the function). (Quick reminder: this is because of how borrowing works. See this StackOverflow question)

This is the same reason why you cannot dereference variables a_item and b_item on the lines with comments.

My question is: is there a way to solve this problem while keeping the generic type? It is almost paradoxical, as it is a very simple task in theory - "just move the ownership of an element from one vector to another" - but due to the ownership rules, this isn't as straightforward.

Answer 1

You can iterate through a Vec while claiming ownership of the elements without consuming the original Vec itself by using .drain(..):

fn my_merge<T: std::cmp::PartialOrd>(a: &mut Vec<T>, b: &mut Vec<T>) -> Vec<T> {
    let mut res: Vec<T> = Vec::new();
    let mut a_iter = a.drain(..);
    let mut b_iter = b.drain(..);

    while let (Some(a_item), Some(b_item)) = (a_iter.next(), b_iter.next()) {
        if a_item <= b_item {
            res.push(a_item);
        } else {
            res.push(b_item);
        }        
    }

    res
}

This of course will leave the inputs (a and b) empty but with their original capacity after merging.