CTCI Challange, DAY 12

Day 12:- 

Problem Statement:-Merge Sort: Counting Inversions

practiced the mergesort before going to solve the problem,It was very easy.

Solution:-

public class Inversions {

    static long countInversions(int[] arr) {
        MergeSort mr = new MergeSort();
        return mr.mergesort(arr);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int arr_i = 0; arr_i < n; arr_i++) {
                arr[arr_i] = in.nextInt();
            }
            long result = countInversions(arr);
            System.out.println(result);
        }
        in.close();
    }

    private static long merge(int[] a, int[] aux, int lo, int mid, int hi) {
        long inversions = 0;

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                inversions += (mid - i + 1);
            } else a[k] = aux[i++];
        }
        return inversions;
    }

}

class MergeSort {

    public long mergesort(int[] array) {
        int[] helper = new int[array.length];
        return mergesort(array, helper, 0, array.length - 1);
    }

    public long mergesort(int[] array, int[] helper, int low, int high) {
        long count = 0;
        if (low < high) {
            int middle = (low + high) / 2;
            count += mergesort(array, helper, low, middle); // Sort left half
            count += mergesort(array, helper, middle + 1, high); // Sort right half
            count += merge(array, helper, low, middle, high); // Merge them
        }
        return count;
    }

    /*public long merge(int[] array, int[] helper, int low, int middle, int high) {

*//* Copy both halves into a helper array *//*
        for (int i = low; i <= high; i++) {
            helper[i] = array[i];
        }

        int helperLeft = low;
        int helperRight = middle + 1;
        int current = low;

*//* Iterate through helper array. Compare the left and right
         * half, copying back the smaller element from the two halves
* into the original array. *//*
        while (helperLeft <= middle && helperRight <= high) {
            if (helper[helperLeft] <= helper[helperRight]) {
                array[current] = helper[helperLeft];
                helperLeft++;
            } else { // If right element is smaller than left element
                array[current] = helper[helperRight];
                helperRight++;
                count++;
            }
            current++;
        }

*//* Copy the rest of the left side of the array into the
         * target array *//*

        int remaining = middle - helperLeft;
        count += remaining;
        for (int i = 0; i <= remaining; i++) {
            array[current + i] = helper[helperLeft + i];
        }
        int remaining1 = high - helperRight;
        for (int i = 0; i <= remaining1; i++) {
            array[current + i] = helper[helperLeft + i];
        }
        return count;
    }*/

    private static long merge(int[] a, int[] aux, int lo, int mid, int hi) {
        long inversions = 0;
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (aux[j] < aux[i]) {
                a[k] = aux[j++];
                inversions += (mid - i + 1);
            } else a[k] = aux[i++];
        }
        return inversions;
    }
}