15. Inversion count

15. Inversion count

Problem link :- click here

package programs;

import java.util.*;

public class Array__15
{

	static int merge(int arr[], int left, int mid, int right)
	{
		int inversion_count=0;
		
		int n1 = mid - left;
		int n2 = right - mid + 1;
		
		int a[] = new int[n1];
		int b[] = new int[n2];
		
		int i, j, k;
		j = left;
		for(i=0; i<n1; i++)
		{
			a[i] = arr[j];
			j++;
		}
		for(i=0; i<n2; i++)
		{
			b[i] = arr[j];
			j++;
		}
		
		i = 0;
		j = 0;
		k = left;
		
		while(  i<n1 &&  j<n2  )
		{
			if( a[i] <= b[j] )
				arr[k++] = a[i++];
			else
			{
				inversion_count = inversion_count + (n1 - i);
				arr[k++] = b[j++];
			}
		}
		
		while(i < n1)
			arr[k++] = a[i++];
		while(j < n2)
			arr[k++] = b[j++];
		
		return inversion_count;
	}
	
	
	static int mergeSort(int arr[], int left, int right)
	{
		int inversion_count=0;
		if(left<right)
		{
			int mid = left + (right - left)/2;
			inversion_count += mergeSort(arr, left, mid);
			inversion_count += mergeSort(arr, mid+1, right);
			
			inversion_count += merge(arr, left, mid+1, right);
		}
		return inversion_count;
	}
	
	public static void main(String[] args)
	{
		int i, n, ans;
		
		Scanner s = new Scanner(System.in);
		System.out .println("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array\n");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given array :");
		print_array(array, n);
		System.out.println("\n");

		ans = mergeSort(array, 0, n-1);
		System.out.println("Inversion Count : " + ans);
	}

	static void print_array(int[] arr, int n)
	{
		for(int i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n logn)
Space complexity :- O(n)