merge.java

import java.util.*;

class Solution {
    public static long countInversions(int[] a){ //expects an array of ints
       
        int n = a.length; //n = length of array
        
        // Base Case
        if(n <= 1) {
            return 0;
        }
        
        // Recursive Case
        //int mid = n >> 1;
        
        int mid = n/2; //get teh middle of the array
        
        int[] left = Arrays.copyOfRange(a, 0, mid); // copy every thing from beginning to middle
        int[] right = Arrays.copyOfRange(a, mid, a.length); //copy everything from middle to end
        long inversions = countInversions(left) + countInversions(right); // long = maxChar 32 bits yet int is only 16
        
        int range = n - mid; //length - mid
        int iLeft = 0;
        int iRight = 0;

        //check which is larger
        for(int i = 0; i < n; i++) { //for every variable in n

            if(
                iLeft < mid 
                && (
                    iRight >= range || left[iLeft] <= right[iRight] //if the one on the left is less than the on on the right
                )
            ) {
                a[i] = left[iLeft++]; //add the new element to the left+1 (the right)
                inversions += iRight; // adds to the inversions
            }
            else if(iRight < range) { 
                a[i] = right[iRight++];
            }
        }
        
        return inversions;
    }
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); //takes in what is inputted
        int t = scanner.nextInt(); //get the number of arrays it expects
        
        for(int i = 0; i < t; i++){ //loops through all the inputs and gets the arrays only
            int n = scanner.nextInt(); //n gives us the length of the incoming array
            int[] a = new int[n]; //a = empty array with length n
            
            for(int j = 0; j < n; j++){ // loops through next array and adds it to the empty array
                a[j] = scanner.nextInt(); //nextInt = the next interger
            }

            //I've now got the arrays
            
            System.out.println(countInversions(a)); // print the count inversions (YET TO BE DETERMINED)
        }
        
        scanner.close(); //close scanner, just good practice
    }
}