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)
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;
}
User contributions licensed under CC BY-SA 3.0