Mergesort not working

help
1

I was playing with macros a little bit but then I realized something was wrong with my mergesort. Given a slice it only returns a vector with 1 element.

macro_rules! inc {
    (++$arg:ident) => {{
        $arg += 1;
        arg
    }};
    ($arg:ident++) => {{
        let old = $arg;
        $arg += 1;
        old
    }};
}

fn merge(arr1: &[i32], arr2: &[i32]) -> Vec<i32> {
    let mut result = Vec::<i32>::with_capacity(arr1.len() + arr2.len());
    let (mut i1, mut i2) = (0usize, 0usize);
    while i1 + i2 + 1 < arr1.len() + arr2.len() {
        result.push(if arr1[i1] < arr2[i2] {
            arr1[inc!(i1++)]
        } else {
            arr2[inc!(i2++)]
        });
    }
    result
}

pub fn perform(arr: &[i32]) -> Vec<i32> {
    match arr.len() {
        0 | 1 => arr.to_vec(),
        _ => merge(
            &perform(&arr[..arr.len() / 2]),
            &perform(&arr[arr.len() / 2..]),
        ),
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn mergesort() {
        let arr = [1, 0, 2, 9, 3, 8, 4, 7, 5, 6];
        let sa = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        assert_eq!(sa, super::perform(&arr).as_slice());
    }
}

Link: Rust Playground

What could be causing this?

Edit: Changed merge() to:

fn merge(arr1: &[i32], arr2: &[i32]) -> Vec<i32> {
    let mut result = Vec::<i32>::with_capacity(arr1.len() + arr2.len());
    let (mut arr1_iter, mut arr2_iter) = (arr1.iter(), arr2.iter());
    loop {
        match (arr1_iter.next(), arr2_iter.next()) {
            (Some(v1), Some(v2)) => result.push(if v1 < v2 { *v1 } else { *v2 }),
            (None, Some(v2)) => result.push(*v2),
            (Some(v1), None) => result.push(*v1),
            _ => break
        };
    }
    result
}

Problem persists: Rust Playground

2

Because of the + 1 in the while loop that makes it return too early.

3

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.