マージソートをしながら転倒数を求めるテクニック
長さ$ Nの配列の転倒数を$ O(N \log N)で求めることができる。ついでにソートもできる。
code:rust
fn sort_inversion<T: Clone + Ord>(a: &T) -> (usize, Vec<T>) { // 長さが 1 以下のときは、ソートする必要がない
if a.len() <= 1 {
return (0, a.to_vec());
}
// 約半分に分ける(分割統治法)
let half = a.len() / 2;
// 半分に分けた配列について、それぞれソートしつつ転倒数を求める
let (inv1, vec1) = sort_inversion(&ahalf);
let (inv2, vec2) = sort_inversion(&ahalf ..); // 配列をマージしつつ、最終的な転倒数を求める
let mut inv = inv1 + inv2;
let mut result = Vec::with_capacity(a.len());
let mut i1 = 0;
let mut i2 = 0;
while i1 < vec1.len() && i2 < vec2.len() {
// 交換する必要がないため転倒数は増えない
result.push(vec1i1.clone()); i1 += 1;
} else {
result.push(vec2i2.clone()); i2 += 1;
// vec2 の要素が vec1 の要素より前にくるとき、交換が起きている
// ここで vec1 の残りの要素はすべて vec2i2 より大きいため、転倒数はその大きさ分増える inv += vec1.len() - i1;
}
}
// 余ったものを result に追加
result.append(&mut vec1i1 ...to_vec()); result.append(&mut vec2i2 ...to_vec()); (inv, result)
}