Miracle of Algorithm

3 5 1 9 6

3 - 1
5 - 1
9 - 6

int count(int[] data) {
	int count = 0;
	for (int i = 0; i < data.length; i++) {
		for (int j = i + 1; j < data.length; j++) {
			if (data[i] > data[j]) {
				count++;
			}
		}
	}
	return count;
}

3 5 1 9 6
L R            มี 0 Inversion

3 5 1 9 6
      L R      มี 1 Inversion
      6 9

3 5 1 6 9
L L R          มี 2 Inversions
1 3 5

1 3 5 6 9
L L L R R      มี 0 Inversion

class Solution {
	int[] buffer;
	public int solution(int[] data) {
		buffer = new int[data.length];
		return count(data, 0, data.length-1);
	}
	int count(int[] a, int left, int right) {
		if (left >= right) return 0;
		int mid = (left + right) / 2;
		int countLeft = count(a, left, mid);
		int countRight = count(a, mid + 1, right);

		int count = 0;
		for (int k = left, i = left, j = mid + 1; 
			k <= right; k++) {
			boolean useLeft = true;
			if (i<=mid && j<=right && a[i] > a[j]) {
				count += mid - i + 1;
				useLeft = false;
			}
			if (i>mid && j<=right) {
				useLeft = false;
			}
			if (i<=mid && j<=right && a[i] <= a[j]) {
				useLeft = true;
			}
			if (i<=mid && j>right) {
				useLeft = true;
			}
			if (useLeft) {
				buffer[k] = a[i];
				i++;
			} else {
				buffer[k] = a[j];
				j++;
			}
		}
		for (int p = left; p <= right; p++) {
			a[p] = buffer[p];
		}
		return count + countLeft + countRight;
	}
}