Описание задачи

Первая строка содержит число 1≤n≤10^5, вторая — массив A[1…n], содержащий натуральные числа, не превосходящие 10^9. Необходимо посчитать число пар индексов 1≤i<j≤n, для которых A[i]>A[j]. (Такая пара элементов называется инверсией массива. Количество инверсий в массиве является в некотором смысле его мерой неупорядоченности: например, в упорядоченном по неубыванию массиве инверсий нет вообще, а в массиве, упорядоченном по убыванию, инверсию образуют каждые два элемента.)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * Main
 *
 * @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
 * Created on 5/16/21.
 */
public class Main {

    long inversions = 0;

    public static void main(String[] args) {
        Main main = new Main();
        main.run();
    }

    public void run() {
        Scanner scanner = new Scanner(System.in).useDelimiter("\n");
        scanner.nextLine();
        List<Integer> input = Arrays.stream(scanner.nextLine().split("\\s+"))
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        sort(input);

        System.out.println(inversions);
    }

    private List<Integer> sort(final List<Integer> input) {
        if(input.size() == 1) return input;

        int median = input.size() / 2;
        List<Integer> left = input.subList(0, median);
        List<Integer> right = input.subList(median, input.size());

        return merge(sort(left), sort(right));
    }

    private List<Integer> merge(List<Integer> left, List<Integer> right) {
        List<Integer> mergeResult = new ArrayList<>();

        int l = 0, r = 0;
        while (l < left.size() && r < right.size()) {
            if (left.get(l) <= right.get(r)) {
                mergeResult.add(left.get(l));
                l++;
            } else {
                mergeResult.add(right.get(r));
                r++;
                inversions += left.size() - l;
            }
        }

        //Add last elements in one batch
        if (l < left.size()) {
            mergeResult.addAll(left.subList(l, left.size()));
        } else if (r < right.size()) {
            mergeResult.addAll(right.subList(r, right.size()));
        }

        return mergeResult;
    }
}