MergeSort

gistfile1.txt

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

static long countInversions(int[] arr)
{
    long inversionsCount = 0;

   int [] lowerArray = new int [arr.length]; 
   int [] higherArray = new int [arr.length]; //frm mid+1 to high

   inversionsCount = countAndSort (arr, 0, arr.length - 1, lowerArray, higherArray);
   return inversionsCount;
}

static long countAndSort(int [] arr, int low, int high, int [] lowerArray, int [] higherArray)
{
    long totalCount = 0;
    long count = 0;
    if (low < high)
    {
        int mid = low + (high-low) /2;

        long lowerCount = countAndSort (arr, low, mid, lowerArray, higherArray);
        long higherCount = countAndSort (arr, mid+1, high, lowerArray, higherArray);
        totalCount += lowerCount + higherCount + countAndSortMerge (arr, low, mid, high, lowerArray, higherArray);
    } 

    return totalCount;
}

static long countAndSortMerge(int [] arr, int low, int mid, int high, int [] lowerArray, int [] higherArray)
{
    long countInversions = 0;

    for (int i=0; i< (mid-low+1);i++)
    {
        lowerArray[i] = arr [low+i];
    }

    for (int i=0; i< (high-mid);i++)
    {
        higherArray[i] = arr [mid+1+i];
    }

    int lowIndex = 0;
    int highIndex = 0;
    int arrIndex = low;

    while (lowIndex < (mid-low+1) && highIndex < (high-mid))
    {
        if (lowerArray[lowIndex] <= higherArray [highIndex])
        {
            arr[arrIndex] = lowerArray[lowIndex];

            ++lowIndex;
        }
        else
        {
            arr[arrIndex] = higherArray[highIndex];

            ++highIndex;
            countInversions += (mid-low+1 - lowIndex);
        }

        ++arrIndex;
    }


    while (lowIndex < (mid-low+1))
    {
        arr[arrIndex] = lowerArray[lowIndex];

        ++lowIndex;
        ++arrIndex;
    }

    while (highIndex < (high-mid))
    {
        arr[arrIndex] = higherArray[highIndex];

        ++highIndex;
        ++arrIndex;
    }

    System.out.printf("CountandsortMerge inversions - %d", countInversions);
    return countInversions;

}

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] arr = new int[n];

            String[] arrItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int arrItem = Integer.parseInt(arrItems[i]);
                arr[i] = arrItem;
            }

            long result = countInversions(arr);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();

        scanner.close();
    }
}