【Rust】クイックソート

アルゴリズム的にはこれが一番簡単。それでこれが早いのか。。

fn quick_sort(data: Vec<i32>) -> Vec<i32> {

    if data.len() <= 1{
        return data;
    }
    let pivot = data[0];
    let mut left: Vec<i32> = Vec::new();
    let mut right: Vec<i32> = Vec::new();
    let mut result: Vec<i32> = Vec::new();
    let mut same = 0;

    for i in data {
        if i < pivot {
            left.push(i);
        } else if i > pivot {
            right.push(i);
        } else {
            same += 1;
        }
    }
    left = quick_sort(left);
    right = quick_sort(right);
    result.append(&mut left);
    if same != 0 {
        for i in 0..same {
            result.push(pivot);
        }
    }
    result.append(&mut right);

    return result;
}

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

    println!("{:?}", quick_sort(data));
}

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