Mergesort

Main.java

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
/*
5
2 3 9 2 9


10

5 34 2 3 5 65 34 23 23 3
*/
public class Main {

    static long number = 0L;

    public static void main(String[] args) throws FileNotFoundException {
//        Scanner scanner = new Scanner(new File("input"));
        Scanner scanner = new Scanner(System.in);


        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }

//        System.out.println(Arrays.toString(array));
//        System.out.println(Arrays.toString(mergeSort(array)));
        mergeSort(array);
        System.out.println(number);
    }

    public static int[] mergeSort(int[] array) {
        if (array.length > 1) {
            int m = array.length/2;
            int[] left = Arrays.copyOfRange(array, 0, m);
            int[] right = Arrays.copyOfRange(array, m, array.length);
            return merge(mergeSort(left), mergeSort(right));
        } else {
            return array;
        }
    }

    private static int[] merge(int[] a, int[] b) {

        if (a.length == 0) {
            return b;
        }

        if (b.length == 0) {
            return a;
        }

        int[] c = new int[a.length + b.length];

        int i = 0;
        int j = 0;
        int k = 0;
        while (i < a.length && j < b.length ) {
            if (a[i] <= b[j]) {
                c[k] = a[i];
                i++;
            } else {
                number+=a.length - i;
                c[k] = b[j];
                j++;
            }
            k++;
        }
        while (i < a.length)
            c[k++] = a[i++];


        while (j < b.length)
            c[k++] = b[j++];

        return c;
    }

}