Merges two sorted IntoIterator into a sorted Iterator with Rust.

merge.rs

#[inline]
pub fn merge<T, L, R>(left: L, right: R) -> Merge<T, L::IntoIter, R::IntoIter>
where
    T: PartialOrd,
    L: IntoIterator<Item = T>,
    R: IntoIterator<Item = T>,
{
    Merge {
        left: left.into_iter().peekable(),
        right: right.into_iter().peekable(),
    }
}

#[derive(Debug, Clone)]
pub struct Merge<T, L, R>
where
    L: Iterator<Item = T>,
    R: Iterator<Item = T>,
{
    left: core::iter::Peekable<L>,
    right: core::iter::Peekable<R>,
}

impl<T, L, R> Iterator for Merge<T, L, R>
where
    T: PartialOrd,
    L: Iterator<Item = T>,
    R: Iterator<Item = T>,
{
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        match (self.left.peek(), self.right.peek()) {
            (Some(l0), Some(r0)) => {
                if l0 < r0 {
                    self.left.next()
                } else {
                    self.right.next()
                }
            }
            _ => self.left.next().or_else(|| self.right.next()),
        }
    }
}