Count Inversions

/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : The number of inversions.
 * Approach: Merge sort.
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: Sort the part [low, high) with merge sort and count the inversions at the same time.
        static long sortAndCount(int[] values, int[] buffer, int low, int high) {
            if (high - low < 2) {
                return 0;
            }
            int middle = (low + high) / 2;
            long count = sortAndCount(values, buffer, low, middle) + sortAndCount(values, buffer, middle, high);

            // Step 2: Merge the two sorted halves. If the right value is smaller than the left value,
            // it is smaller than ALL remaining left values too. All of them form inversions with it.
            int i = low;
            int j = middle;
            int k = low;
            while (i < middle && j < high) {
                if (values[i] <= values[j]) {
                    buffer[k++] = values[i++];
                } else {
                    buffer[k++] = values[j++];
                    count += middle - i;
                }
            }
            while (i < middle) {
                buffer[k++] = values[i++];
            }
            while (j < high) {
                buffer[k++] = values[j++];
            }
            for (int t = low; t < high; t++) {
                values[t] = buffer[t];
            }
            return count;
        }

    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a) {
        return sortAndCount(a, new int[a.length], 0, a.length);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}