# Untitled

a guest
Sep 20th, 2021
63
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. public class Solution {
2.
3. public long countInversions(int[] arr) {
4.
5. return mergeSort(arr, 0, arr.length - 1);
6.
7. }
8.
9.
10.
11. private long mergeSort(int[] arr, int start, int end) {
12.
13. if (start >= end) {
14.
15. return 0;
16.
17. }
18.
19. int mid = start + (end - start) / 2;
20.
21. int count = 0;
22.
23. count += mergeSort(arr, start, mid);
24.
25. count += mergeSort(arr, mid + 1, end);
26.
27. count += merge(arr, start, mid, end);
28.
29. return count;
30.
31. }
32.
33.
34.
35. private long merge(int[] arr, int start, int mid, int end) {
36.
37. int left = start;
38.
39. int right = mid + 1;
40.
41. int[] tmp = new int[end - start + 1];
42.
43. int k = 0;
44.
45. int count = 0;
46.
47. while (left<= mid && right<= end) {
48.
49. if (arr[left] > arr[right]) {
50.
51. // count inversions between left & right array
52.
53. count += end - right + 1;
54.
55. tmp[k++] = arr[left++];
56.
57. } else {
58.
59. tmp[k++] = arr[right++];
60.
61. }
62.
63. }
64.
65.
66.
67. while (left<= mid) {
68.
69. tmp[k++] = arr[left++];
70.
71. }
72.
73.
74.
75. while (right<= end) {
76.
77. tmp[k++] = arr[right++];
78.
79. }
80.
81. // copy tmp to array, can replace
82.
83. // by System.arraycopy method
84.
85. for (int i = 0; i<tmp.length; i++) {
86.
87. arr[i + start] = tmp[i];
88.
89. }
90.
91. return count;
92.
93. }
94.
95. }
RAW Paste Data