✅Inversion of array(Contest)

Inversion of array medium Time Limit: 2 sec Memory Limit: 128000 kB

Problem Statement :

Given an array of positive integers. The task is to find inversion count of array.

Inversion Count : For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Asked in Adobe, Amazon, Microsoft. Input The first line of each test case is N, the size of the array. The second line of each test case contains N elements.

Constraints:- 1 ≤ N ≤ 10^5 1 ≤ a[i] ≤ 10^5 Output Print the inversion count of array. Example Sample Input: 5 2 4 1 3 5

Sample Output: 3

Explanation: Testcase 1: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

link:https://my.newtonschool.co/playground/code/jm4tqoi5374t

```java
import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    static long count =0;
    static long temp[] = new long[100001];
    public static void merge(long[] arr, int start, int mid, int end){
        for(int i= start;i<=end;i++){
            temp[i]=arr[i];
        }
        int i=start;
        int j=mid+1;
        int index= start;
        while(i<=mid && j<=end){
            if(temp[i]<=temp[j]){
                arr[index]=temp[i];
                i++;
            }
            else{
                arr[index]=temp[j];
                count+=mid+1-i;
                j++;
            }
            index++;
        }
        while(i<=mid){
            arr[index]=temp[i];
            index++;
            i++;
        }
        while(j<=end){
            arr[index]=temp[j];
            index++;
            j++;
        }
    }
    public static void mergeSort(long arr[], int start, int end){
        if(start>=end){
            return;
        }
        int mid=(start)+(end-start)/2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long array[]=new long[n];
        for(int i=0;i<n;i++){
            array[i]=sc.nextLong();

        }
        mergeSort(array,0,n-1);
        System.out.println(count);
        // Your code here
        
    

        
    }
}
```