Rust quick_sort ported from Rosetta code Dart example

quick_sort.rs

use std::fmt::Show;

fn main() {
    println!("After sort: {}", quick_sort(vec!(1u, 5, 2, 7, 3, 9, 4, 6, 8)));
    println!("After sort: {}", quick_sort(vec!(1u, 2, 3, 4, 5, 6, 7, 8, 9)));
    println!("After sort: {}", quick_sort(vec!(9u, 8, 7, 6, 5, 4, 3, 2, 1)));
}

fn quick_sort<T: Clone + Show + PartialOrd>(a: Vec<T>) -> Vec<T> {
    if a.len() <= 1 {
        return a.clone();
    }
    
    let pivot = &a[0].clone();
    
    let mut less = Vec::new();
    let mut more = Vec::new();
    let mut pivot_list = Vec::new();
    
    // Partition
    for i in a.iter() {
        if i < pivot {
            less.push(i.clone());            
        } else if i > pivot {
            more.push(i.clone());
        } else {
            pivot_list.push(i.clone());
        }
    }
    
    // Recursively sort sublists
    less = quick_sort(less);
    more = quick_sort(more);
    
    // Concatenate results
    less.push_all(pivot_list.as_slice());
    less.push_all(more.as_slice());
    
    return less;
}