Quicksort implementation in Rust

quicksort.rs

extern crate time;
extern crate core;
extern crate rand;

use core::fmt::Display;
use rand::Rng;

const SORT_THRESHOLD: usize = 16;
const LIST_SIZE: usize = 10000000;

/*
fn selection_sort<T: PartialOrd>(items: &mut [T]) {
    if items.len() <= 1 {
        return;
    }
    
    for i in (1..items.len()).rev() {
        let mut max_pos = 0;
        for j in 1..i {
            if items[j] > items[max_pos] {
                max_pos = j;
            }
        }
        items.swap(i, max_pos);
    }
}

fn bubble_sort<T: PartialOrd>(items: &mut [T]) {
    loop {
        let mut changed = false;
        for i in 0..(items.len()-1) {
            if items[i] > items[i+1] {
                items.swap(i, i+1);
                changed = true;
            }
        }
        if !changed {
            break;
        }
    }
}
*/

fn insertion_sort<T: PartialOrd>(items: &mut [T]) {
    if items.len() <= 1 {
        return;
    }
    
    for i in 1..items.len() {
        for j in (0..i).rev() {
            if items[j] > items[j+1] {
                items.swap(j, j+1);
            } else {
                break;
            }
        }
    }
}

fn partition<T: PartialOrd + Display>(pos: usize, items: &mut [T]) -> usize {
    let mut partition = pos;
    let mut i = 0;

    loop {
        if i >= partition {
            break;
        }

        if items[i] > items[partition] {
            items.swap(partition, partition-1);
            if i < partition-1 {
                items.swap(i, partition);
            }
            partition -= 1;
        } else {
            i += 1;
        }
    }

    i = items.len()-1;
    loop {
        if i <= pos || i <= partition {
            break;
        }

        if items[i] < items[partition] {
            items.swap(partition, partition+1);
            if i > partition+1 {
                items.swap(i, partition);
            }
            partition += 1;
        } else {
            i -= 1;
        }
    }
    partition
}

fn quick_sort<T: PartialOrd + Display>(items: &mut [T]) {
    if items.len() < 1 {
        return;
    }

    if items.len() < SORT_THRESHOLD {
        return insertion_sort(items);
    }

    let pos = partition(items.len() / 2, items);
    let (first, second) = items.split_at_mut(pos);
    quick_sort(first);
    quick_sort(second);
}

#[allow(dead_code)]
fn display<T: Display>(items: &[T]) {
    print!("[ ");
    for i in 0..(items.len()-1) {
        print!("{:3}, ", items[i]);
        if (i+1) % 40 == 0 {
            print!("\n  ");
        }
    }
    println!("{}]", items[items.len()-1]);
}

fn verify<T: PartialOrd>(items: &[T]) -> i32 {
    for i in 0..(items.len()-1) {
        if items[i] > items[i+1] {
            return i as i32;
        }
    }
    return -1;
}

fn main() {
    let mut rng = rand::thread_rng();
    let mut items: Vec<u32> = Vec::new();

    for _ in 0..LIST_SIZE {
        let num = rng.gen_range(1, LIST_SIZE+1) as u32;
        items.push(num);
    }
    let mut items_copy: Vec<u32> = items.clone();

    println!("Start");
    let start = time::precise_time_s();
    items_copy.sort();
    let end = time::precise_time_s();
    println!("End");

    println!("Default Sort Duration: {}", end - start);

    println!("Verified: {}", verify(&items) == -1);
    //display(&items);
    println!("Start");
    let start = time::precise_time_s();
    quick_sort(&mut items);
    let end = time::precise_time_s();
    println!("End");

    println!("Quicksort Duration: {}", end - start);
    println!("Verified: {}", verify(&items) == -1);
    //display(&items);
}