Why does my recursive merge sort algorithm result in a stack overflow?

-2

A recursive call while implementing merge sort throws an error. I tried using debug macros to see if its some memory restriction without luck.

fn merge<T: PartialOrd>(mut v: Vec<T>) -> Vec<T> {
    if v.len() < 1 {
        return v;
    }
    let mut res = Vec::with_capacity(v.len());
    let b = v.split_off(v.len() / 2);
    let a = merge(v);
    let b = merge(b);
    let mut a_it = a.into_iter();
    let mut b_it = b.into_iter();
    let mut a_curr = a_it.next();
    let mut b_curr = b_it.next();
    loop {
        match a_curr {
            Some(ref a_val) => match b_curr {
                Some(ref b_val) => {
                    if a_val < b_val {
                        res.push(a_curr.take().unwrap());
                        a_curr = a_it.next()
                    } else {
                        res.push(b_curr.take().unwrap());
                        b_curr = b_it.next();
                    }
                }
                None => {
                    res.push(a_curr.take().unwrap());
                    res.extend(a_it);
                    return res;
                }
            },
            None => {
                if let Some(b_val) = b_curr {
                    res.push(b_val)
                }
                res.extend(b_it);
                return res;
            }
        }
    }
}

fn main() {
    let v = vec![9, 7, 4, 6, 5, 2, 1, 11];
    let x = merge(v);
    println!("{:?}", x);
}
thread 'main' has overflowed its stack
error: process didn't exit successfully: `target\debug\tescode.exe` (exit code: 0xc00000fd, STATUS_STACK_OVERFLOW)
algorithm
sorting
rust
asked on Stack Overflow Feb 16, 2021 by KaranV • edited Feb 16, 2021 by Shepmaster

1 Answer

4

You have a stack overflow because you perform an infinite number of recursive calls. This is caused by the fact that your exit criteria is incorrect; use less-than-or-equal instead:

if v.len() <= 1 {
    return v;
}
answered on Stack Overflow Feb 16, 2021 by Shepmaster

User contributions licensed under CC BY-SA 3.0