Parallel qsort

lib.rs

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

extern crate scoped_pool;
use scoped_pool::{Pool, Scope};


/// 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| {
        scope.recurse(move |scope| { parallel_qsort(arr, &scope); });
    });
}

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

    let (left, right) = arr.split_at_mut(p);
    
    if left.len() > 1 {
        scope.recurse(move |scope| { parallel_qsort(left, scope); });
    }

    if right.len() > 1 {
        scope.recurse(move |scope| { parallel_qsort(right, scope); });
    }
}

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();
    }
}