I've just started learning Rust and put together this working MergeSort implementation. Wondering what I've overlooked and what I could improve.
I couldn't figure out a cleaner way to deal with the Option
type returned by the iterator than just checking that values weren't None
and then .unwrap()
ing my results but I'd really appreciate any suggestions.
Included working test cases. Let me know if there's a case I missed.
pub fn merge_sort(mut input: Vec<usize>) -> Vec<usize> {
let length = input.len();
// Base case
if length < 2 {
return input;
}
let right = merge_sort(input.split_off(length / 2));
let left = merge_sort(input);
let mut left_iter = left.iter().peekable();
let mut right_iter = right.iter().peekable();
let mut merged = Vec::new();
let mut i = 0;
while i < length {
if left_iter.peek() > right_iter.peek() && right_iter.peek() != None {
merged.push(*(right_iter.next().unwrap()));
} else if left_iter.peek() != None {
merged.push(*(left_iter.next().unwrap()));
}
i += 1;
}
merged
}
#[cfg(test)]
mod tests {
use merge_sort;
#[test]
fn it_works() {
assert_eq!(merge_sort(vec![4, 3]), vec![3, 4]);
}
#[test]
fn test_base_case() {
assert_eq!(merge_sort(vec![3]), vec![3]);
}
#[test]
fn totally_backwards() {
assert_eq!(
merge_sort(vec![100, 90, 50, 14, 9, 7, 3]),
vec![3, 7, 9, 14, 50, 90, 100]
);
}
}
beta
.)) \$\endgroup\$