in place radix sort of 1 million u8 integers

radix_sort.rs

extern crate rand;

const N : usize = 1_000_000;
//const N : usize = 20;

#[inline(always)]
fn test_bit(x: u8, bit: u8) -> bool {
    (x & bit) != 0
}

// used for debug
fn vec_of_slice<T:Copy>(a: &[T]) -> Vec<T> {
    a.iter().map(|&x| x).collect::<Vec<T>>()
}

fn radix_sort(a: &mut [u8], bit: u8) {
    //println!("radix-sort {:?}, bit {}", vec_of_slice(a), bit);
    if a.len() <= 1 { return; } // trivial
    let mut i = 0;
    let mut j = a.len() - 1;
    // invariant: `a[..i]` all have 0 for `bit`; `a[j+1..]` all have 1 for `bit`
    loop {
        while i < a.len() && !test_bit(a[i], bit) { i += 1 }
        while j > 0 && test_bit(a[j], bit) { j -= 1 }

        if i >= j {
            break
        } else {
            debug_assert!(test_bit(a[i], bit) && !test_bit(a[j], bit));
            a.swap(i, j);
            continue;
        }
    }
    assert!(i >= j);
    // sort sub-arrays
    if bit > 1 {
        radix_sort(&mut a[..i], bit >> 1);
        radix_sort(&mut a[i..], bit >> 1);
    }
}

fn sorted(a: &[u8]) -> bool {
    a.iter().zip(a.iter().skip(1)).all(|(x,y)| x <= y)
}

fn main() {
    let mut a : [u8; N] = [0; N];
    for i in 0 .. N { a[i] = rand::random::<u8>(); };
    println!("sort random array");
    radix_sort(&mut a, 1 << 7);
    println!("check sorted");
    assert!(sorted(&a), "{:?}", vec_of_slice(&a));
}