Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
MergeSort
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.