Method sort_i32

src/strings/lsd.rs:85–127

(a: &mut [i32])

    }

    pub fn sort_i32(a: &mut [i32]) {
        let BITS = 32;
        let MASK = R_I32 - 1;
        let w = BITS / BITS_PER_BYTE;

        let n = a.len();
        let mut aux = vec![0; n];
        for d in 0..w {
            // compute frequency counts
            let mut count = [0; R_I32 + 1];
            for it in a.iter().take(n) {
                let c = *it >> (BITS_PER_BYTE * d) & MASK as i32;
                count[c as usize + 1] += 1;
            }

            // compute cumulates
            for r in 0..R_I32 {
                count[r + 1] += count[r];
            }

            // for most significant byte, 0x80-0xFF comes before 0x00-0x7F
            if d == w - 1 {
                let shift1 = count[R_I32] - count[R_I32 / 2];
                let shift2 = count[R_I32 / 2];
                for it in count.iter_mut().take(R_I32 / 2) {
                    *it += shift1;
                }
                for it in count.iter_mut().take(R_I32).skip(R_I32 / 2) {
                    *it -= shift2;
                }
            }

            // move data
            for it in a.iter().take(n) {
                let c = *it >> (BITS_PER_BYTE * d) & MASK as i32;
                aux[count[c as usize]] = *it;
                count[c as usize] += 1;
            }

            // copy back
            a[..n].clone_from_slice(&aux[..n]);
        }
    }
}