【Rust】マージソート

大容量データの計算量が早い。

fn merge_sort(data: Vec<usize>) -> Vec<usize>{
    if data.len() <= 1 {
        return data;
    }
        
    let mid = data.len() / 2;
    let mut left: Vec<usize> = merge_sort(data[0..mid].to_vec());
    let mut right: Vec<usize>  = merge_sort(data[mid..].to_vec());

    return merge(left, right);
}

fn merge(left: Vec<usize>, right: Vec<usize>) -> Vec<usize> {
    let mut result: Vec<usize> = Vec::new();

    let mut i = 0;
    let mut j = 0;

    while (i < left.len()) && (j < right.len()) {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }

    if i < left.len() {
        result.append(&mut left[i..].to_vec());
    }
    if j < right.len() {
        result.append(&mut right[j..].to_vec());
    }
    return result;
}

fn main() {
    let mut data = vec![6, 15, 4, 2, 8, 5, 11, 9, 7, 13];
    println!("{:?}", merge_sort(data));
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.23s
Running `target/debug/rust`
[2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

何だこれは… 凄いな