merge_sort.rs

use std::fmt::Debug;

fn merge<T>(left: &mut Vec<T>, right: &mut Vec<T>) -> Vec<T> where T: Ord + Clone + Debug {
    let mut result: Vec<T> = Vec::new();

    while !left.is_empty() && !right.is_empty() {
        if left[0] <= right[0] {
            result.push(left[0].clone());
            left.remove(0);
        } else {
            result.push(right[0].clone());
            right.remove(0);
        }
    }

    result.append(left);
    result.append(right);

    result
}

fn merge_sort<T>(elements: &Vec<T>) -> Vec<T> where T: Ord + Clone + Debug {
    if elements.len() <= 1 {
        return elements.clone();
    }

    let mut left = Vec::new();
    let mut right = Vec::new();

    for (i, e) in elements.iter().enumerate() {
        if i % 2 == 1 {
            left.push(e.clone());
        } else {
            right.push(e.clone());
        }
    }

    let mut new_left = merge_sort(&left);
    let mut new_right = merge_sort(&right);

    merge(&mut new_left, &mut new_right)
}

fn main() {
    let mut e: Vec<char> = Vec::new();
    e.push('c');
    e.push('z');
    e.push('a');
    let sorted = merge_sort(&e);
    println!("{:?}", sorted);
}