К
Size: a a a
b
b
b
b
А⚙
А⚙
А⚙
b
А⚙
b
b
b
b
b
b
b
let rs_step_asc [n] ((xs:[n]u32,is:[n]i32),bitn:i32) : ([n]u32,[n]i32) =
let bits1 = map (\x -> (i32.u32 (x >> u32.i32 bitn)) & 1) xs
let bits0 = map (1-) bits1
let idxs0 = map2 (*) bits0 (scan (+) 0 bits0)
let idxs1 = scan (+) 0 bits1
let offs = reduce (+) 0 bits0 -- store idxs1 last
let idxs1 = map2 (*) bits1 (map (+offs) idxs1)
let idxs = map (\x->x-1) (map2 (+) idxs0 idxs1)
in (scatter (copy xs) idxs xs,
scatter (copy is) idxs is)
-- Radix sort - ascending
let rsort_asc [n] (xs: [n]u32) : ([n]u32,[n]i32) =
let is = iota n
in loop (p : ([n]u32,[n]i32)) = (xs,is) for i < 32 do
rs_step_asc(p,i)
b