クイックソート

code:rust

use rand::*;

if slice.len() <= 1 {

return;

}

// pivot を先頭に持ってくる

slice.swap(0, rng().random_range(0 .. slice.len()));

// pivot 以下の要素が先頭の r 個となるようにする

let mut r = 1;

for i in 1 .. slice.len() {

slice.swap(r, i);

r += 1;

}

}

// pivot と等しい値を真ん中に持ってくる（同じ値が多い場合の計算量悪化回避）

let mut l = r - 1;

slice.swap(0, l);

for i in (0 .. r - 1).rev() {

l -= 1;

slice.swap(i, l);

}

}

// 再帰的にソート

}