Count of Smaller Numbers After Self LeetCode solution in Rust

1
fn merge_sort(nums: &mut Vec<(usize, i32)>, l: usize, r: usize, ans: &mut Vec<i32>) {
2
  if l < r - 1 {
3
    let m = l + (r - l) / 2;
4
    merge_sort(nums, l, m, ans);
5
    merge_sort(nums, m, r, ans);
6
    merge(nums, l, m, r, ans);
7
  }
8
}
9

10
fn merge(nums: &mut Vec<(usize, i32)>, l: usize, m: usize, r: usize, ans: &mut Vec<i32>) {
11
  let mut arr = Vec::with_capacity(r - l);
12
  let mut i = l;
13
  let mut j = m;
14
  let mut ct = 0;
15
  while i < m && j < r {
16
    if nums[i].1 <= nums[j].1 {
17
      ans[nums[i].0] += ct;
18
      arr.push(nums[i]);
19
      i += 1;
20
    } else {
21
      ct += 1;
22
      arr.push(nums[j]);
23
      j += 1;
24
    }
25
  }
26
  while i < m {
27
    ans[nums[i].0] += (r - m) as i32;
28
    arr.push(nums[i]);
29
    i += 1;
30
  }
31
  while j < r {
32
    arr.push(nums[j]);
33
    j += 1;
34
  }
35

36
  for (i, n) in arr.into_iter().enumerate() {
37
    nums[l + i] = n;
38
  }
39
}
40

41
impl Solution {
42
  pub fn count_smaller(nums: Vec<i32>) -> Vec<i32> {
43
    let len = nums.len();
44
    let mut ans = vec![0; len];
45
    let mut nums = nums.into_iter().enumerate().collect();
46
    merge_sort(&mut nums, 0, len, &mut ans);
47
    ans
48
  }
49
}