Parallel qsort

lib.rs

use std::cmp::Ordering;
use std::fmt::Debug;

extern crate scoped_pool;
use scoped_pool::Pool;


/// An insertion sort for small slices
#[inline]
fn insertion_sort<T>(arr: &mut [T], left: usize, right: usize) where T: Ord {
	for i in (left + 1)..(right + 1) {
		let mut j = i;
		while j > left && arr[j].cmp(&arr[j - 1]) == Ordering::Less {
			arr.swap(j, j - 1);
			j = j - 1;
		}
	}
}

#[inline]
pub fn par_qsort<T>(arr: &mut [T]) where T: Ord + Send + Debug {
	let pool = Pool::new(4);
	pool.scoped(|scope| {
	    let my_pool = pool.clone();
	    scope.execute(move || { parallel_qsort(arr, my_pool); });
	    scope.join();
	});
}

pub fn parallel_qsort<T>(arr: &mut [T], pool: Pool) where T: Ord + Send + Debug {
	
	let p = partition(arr);

	let (left, right) = arr.split_at_mut(p);
	
	pool.scoped(|scope| {
		if left.len() > 1 {
	    	let my_pool = pool.clone();
	    	scope.execute(move || { parallel_qsort(left, my_pool); });
		}
	
		if right.len() > 1 {
	    	let my_pool = pool.clone();
	    	scope.execute(move || { parallel_qsort(right, my_pool); });
		}
	});
}

fn partition<T>(arr: &mut [T]) -> usize where T: Ord + Send + Debug {
	unsafe {
		let pivot_idx = arr.len() - 1;
		let pivot : *mut T = &mut arr[pivot_idx];
		let mut i = 0;
		for j in 0..pivot_idx {
			match arr[j].cmp(&*pivot) {
				Ordering::Less | Ordering::Equal => { arr.swap(j, i); i = i + 1 },
				_ => {continue}
			}
		}
		arr.swap(i, pivot_idx);
		i
	}
}

 
#[cfg(test)]
extern crate rand;

#[cfg(test)]
pub mod tests {
    use rand::{self, Rng};
    use super::par_qsort;

    #[test]
    pub fn random() {
        let mut rng = rand::thread_rng();
        for _ in 0u32 .. 50000u32 {
            let len: usize = rng.gen();
            let mut v: Vec<isize> = rng.gen_iter::<isize>().take((len % 64) + 1).collect();
            par_qsort(&mut v);
            for i in 0 .. v.len() - 1 {
                assert!(v[i] <= v[i + 1])
            }
        }
    }

	#[test]
	pub fn bench_quicksort1() {
		let mut rng = rand::thread_rng();
		let len: usize = 20000000;
	    let mut v: Vec<isize> = rng.gen_iter::<isize>().take(len).collect();
	    par_qsort(&mut v);
	}

	#[test]
	pub fn bench_quicksort2() {
		let len: usize = 7000;
	    let mut v: Vec<usize> = (0..len).collect();
	    par_qsort(&mut v);
	}

	#[test]
	pub fn bench_sort() {
		let mut rng = rand::thread_rng();
		let len: usize = 20000000;
	    let mut v: Vec<isize> = rng.gen_iter::<isize>().take(len).collect();
	    v.sort();
	}


	#[test]
	pub fn bench_sort2() {
		let len: usize = 7000;
	    let mut v: Vec<usize> = (0..len).collect();
	    v.sort();
	}
}