Inversion counter version in C#. This is optimized version. It uses merge sort to count number of inversions. Hence it's O(n*logn)

InversionCounter.cs

public class InversionCounter
{
    List<int> array;

    public InversionCounter (IEnumerable<int> arr)
    {
        array = arr.ToList();
    }

    private Tuple<int, List<int>> Merge(List<int> leftList, List<int> rightList) 
    {
        int i = 0;
        int j = 0;
        int count = 0;
        List<int> mergedList = new List<int>();

        while (i < leftList.Count &&
               j < rightList.Count)
        {
            if (leftList[i] <= rightList[j])
            {
                mergedList.Add(leftList[i]);
                i++;
            }
            else
            {
                count++; 
                mergedList.Add(rightList[j]);
                j++;
            }
        }
        
        if(i == leftList.Count)
        {
            mergedList.AddRange(rightList.GetRange(j , rightList.Count-1));
        }
        else
        {
            count += (leftList.Count - i); 
            mergedList.AddRange(leftList.GetRange(i, leftList.Count - 1));
        }
        return new Tuple<int,List<int>>(count, mergedList);
    }

    private Tuple<int, List<int>> MergeInversion(List<int> list) 
    {
        if(list.Count <= 1)
        {
            return new Tuple<int,List<int>>(0, list);
        }

        int mid = list.Count / 2;
        var leftTuple = MergeInversion(list.GetRange(0, mid));
        var rightTuple = MergeInversion(list.GetRange(mid, (list.Count-mid)));
        var mergedTuple = Merge(leftTuple.Item2, rightTuple.Item2);
        int inversions = leftTuple.Item1 + rightTuple.Item1 + mergedTuple.Item1;
        return new Tuple<int,List<int>>(inversions, mergedTuple.Item2);
    }

    public int GetInversion() 
    {
        return MergeInversion(array).Item1;
    }
}