For this problem I have a java code:

import java.util.Arrays; import java.util.Scanner; public class MergeSortWeightedSumInversion { public static long merge(int arr[], int l, int mid, int r) { long weight = 0; int n1 = mid-l+1; int n2 = r-mid; int[] a = new int[n1]; int[] b = new int[n2]; for(int i = 0; i This is wrong because I tried testing it on the array: [7,3,8,1,5] and I got a weight of 26, its only adding up half of the inversions. How would I modify it so that it works? Code in java and time complexity must be O(n log(n)) please.

In the problem of counting inversions, you are given a permutation a1,a2,an of numbers 1,2,,n, and the goal is to count the number of pairs i,j, where iaj. In this homework problem, you are given a sequence of n numbers b1,b2,,bn and your task is to compute the "weighted count" of inversions defined as follows: An inversion is a pair of indices i,j where ibj. An i,j inversion has weight bi+bj and the weighted count for the input sequence is the sum of the weights of all its inversions. For example, for n=5 and input sequence 7,3,8,1,5, we have the following inversions weights: 7+3=10,7+1=8,7+5=12,3+1=4,8+1=9, and 8+5=13. The overall weighted count is: 10+8+12+4+9+13=56. Design an O(nlogn) algorithm which computes the weighted count of inversions for a given input sequence