Merge sort ported from the C# example

merge_sort.rs

fn main() {
     let list: Vec<u64> = vec![1, 2, 3, 6, 8, 8, 4, 5, 99, 234, 4, 1, 2, 45];
     let sorted = sort(list);
     println!("sorted: {}", sorted);
     
     // sorted: [1, 1, 2, 2, 3, 4, 4, 5, 6, 8, 8, 45, 99, 234]
}

fn sort<T: Clone + PartialOrd>(list: Vec<T>) -> Vec<T> {
    if list.len() <= 1 { 
        return list;
    }
    
    let left_slice = list.slice(0u, list.len() / 2);
    let right_slice = list.slice(left_slice.len(), list.len());
    
    let mut left: Vec<T> = Vec::with_capacity(left_slice.len());
    let mut right: Vec<T> = Vec::with_capacity(right_slice.len());
    
    left.push_all(left_slice);
    right.push_all(right_slice);
    
    return merge(&mut sort(left), &mut sort(right));
}

fn merge<T: PartialOrd + Clone>(left: &mut Vec<T>, right: &mut Vec<T>) -> Vec<T> {
    let mut result: Vec<T> = Vec::with_capacity(left.len() + right.len());
    
    while left.len() > 0 && right.len() > 0 {
        if left[0] <= right[0] {
            result.push(left[0].clone());
            left.remove(0u);
        } else {
            result.push(right[0].clone());
            right.remove(0u);
        }
    }
    result.push_all(left.as_slice());
    result.push_all(right.as_slice());
    
    return result;
}