Calculates inversion numbers of sequence with Rust.

inversions.rs

pub fn inversions(nums: &[usize]) -> Vec<usize> {
    let len = nums.len();
    let mut counts = SegTree::<Sum>::new(len);
    let mut inversions = Vec::with_capacity(len);
    for (i, &num) in nums.into_iter().enumerate() {
        let Sum(inv) = counts.query(0..num);
        inversions.push(i - inv);
        counts.insert(num, Sum(1));
    }
    inversions
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Sum(usize);

impl Monoid for Sum {
    const ID: Self = Self(0);
    fn op(self, other: Self) -> Self {
        Self(self.0 + other.0)
    }
}

// SegTree: https://gist.github.com/MikuroXina/e03ad92e7274891061a344a68e63a3dd

only-one-conquer.rs

// Find an inversions of number by divide-and-conquer method.

pub fn inversions(nums: &[usize]) -> usize {
    sort_and_count(nums).0
}

fn sort_and_count(nums: &[usize]) -> (usize, Vec<usize>) {
    if nums.len() <= 1 {
        return (0, nums.to_vec());
    }
    let (first, last) = nums.split_at(nums.len() / 2);
    let (first_inv, first_sorted) = sort_and_count(first);
    let (last_inv, last_sorted) = sort_and_count(last);
    let (merged_inv, merged) = merge_and_count(&first_sorted, &last_sorted);
    (first_inv + last_inv + merged_inv, merged)
}

fn merge_and_count(first: &[usize], last: &[usize]) -> (usize, Vec<usize>) {
    let mut first_idx = 0;
    let mut last_idx = 0;
    let mut count = 0;
    let mut merged = Vec::with_capacity(first.len() + last.len());
    while first_idx < first.len() && last_idx < last.len() {
        if first[first_idx] < last[last_idx] {
            merged.push(first[first_idx]);
            first_idx += 1;
        } else {
            merged.push(last[last_idx]);
            last_idx += 1;
            count += first.len() - first_idx;
        }
    }
    merged.extend(&first[first_idx..]);
    merged.extend(&last[last_idx..]);
    (count, merged)
}