Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- public long countInversions(int[] arr) {
- return mergeSort(arr, 0, arr.length - 1);
- }
- private long mergeSort(int[] arr, int start, int end) {
- if (start >= end) {
- return 0;
- }
- int mid = start + (end - start) / 2;
- int count = 0;
- count += mergeSort(arr, start, mid);
- count += mergeSort(arr, mid + 1, end);
- count += merge(arr, start, mid, end);
- return count;
- }
- private long merge(int[] arr, int start, int mid, int end) {
- int left = start;
- int right = mid + 1;
- int[] tmp = new int[end - start + 1];
- int k = 0;
- int count = 0;
- while (left<= mid && right<= end) {
- if (arr[left] > arr[right]) {
- // count inversions between left & right array
- count += end - right + 1;
- tmp[k++] = arr[left++];
- } else {
- tmp[k++] = arr[right++];
- }
- }
- while (left<= mid) {
- tmp[k++] = arr[left++];
- }
- while (right<= end) {
- tmp[k++] = arr[right++];
- }
- // copy tmp to array, can replace
- // by System.arraycopy method
- for (int i = 0; i<tmp.length; i++) {
- arr[i + start] = tmp[i];
- }
- return count;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement