BOJ. Bubble Sort (1517)

Problem

A pair of indices (i, j) with i < j and A[i] > A[j] is an inversion. In bubble sort, each adjacent swap exchanges an out-of-order pair; that pair is then in sorted order and is never swapped again. The process removes every inversion, one per swap, so the total number of swaps is exactly the inversion count.

Merge sort counts those pairs without simulating swaps. Once the two halves are sorted, if the current right value is smaller than the current left value, it is smaller than every remaining value in the left half. Add the number of remaining left values to the answer before copying that right value. On equality, take the left value first: equal values do not form an inversion. Recursive calls count inversions within each half, while this merge counts only cross-half inversions.

The runtime is O(N log N) and the input plus merge buffer use O(N) space. The result uses long, since the maximum inversion count is N(N - 1) / 2.

import java.io.*;

public class Main {
  static class FastScanner {
    private final InputStream input;
    private final byte[] buffer = new byte[1 << 16];
    private int length = 0;
    private int pointer = 0;

    FastScanner(InputStream input) {
      this.input = input;
    }

    private int read() throws IOException {
      if (pointer == length) {
        length = input.read(buffer);
        pointer = 0;
        if (length == -1) return -1;
      }
      return buffer[pointer++];
    }

    int nextInt() throws IOException {
      int c;
      do {
        c = read();
      } while (c <= ' ' && c != -1);

      int sign = 1;
      if (c == '-') {
        sign = -1;
        c = read();
      }

      int value = 0;
      while (c > ' ') {
        value = value * 10 + c - '0';
        c = read();
      }
      return value * sign;
    }
  }

  static int[] values;
  static int[] buffer;

  static long sortAndCount(int left, int right) {
    if (right - left <= 1) return 0;

    int middle = left + (right - left) / 2;
    long count = sortAndCount(left, middle) + sortAndCount(middle, right);

    int i = left;
    int j = middle;
    int out = left;
    while (i < middle && j < right) {
      if (values[i] <= values[j]) {
        buffer[out++] = values[i++];
      } else {
        buffer[out++] = values[j++];
        count += middle - i;
      }
    }
    while (i < middle) buffer[out++] = values[i++];
    while (j < right) buffer[out++] = values[j++];
    System.arraycopy(buffer, left, values, left, right - left);

    return count;
  }

  public static void main(String[] args) throws IOException {
    FastScanner input = new FastScanner(System.in);
    int n = input.nextInt();
    values = new int[n];
    buffer = new int[n];
    for (int i = 0; i < n; i++) values[i] = input.nextInt();

    System.out.println(sortAndCount(0, n));
  }
}