Array Presets
Algorithm Loop
The Merge Trick
Both the left and right halves are already sorted. If we find that
arr[i] > arr[j],
then every element from i to the end of the left
half
is also greater than arr[j].
We instantly count all of them: +(mid - i + 1)
inversions!
Live Console Log
Total Inversions
Inversion Count via Merge Sort
An inversion is a pair of elements (i, j) such that i < j and
arr[i] > arr[j]. A brute-force approach checks every pair, taking
$O(N^2)$ time. By modifying the Merge Sort algorithm, we can count inversions in
$O(N \log N)$ Time and $O(N)$ Space.
Divide & Conquer
We divide the array into two halves, recursively counting inversions in the left half, right
half, and cross-inversions that span across the two halves during the merge step.
Total inversions = inv_left + inv_right + inv_merge.
The Merge Counting Logic
While merging two sorted subarrays (left: i to mid, right:
j to end), if arr[i] > arr[j], we have found an
inversion. Crucially, because the left subarray is sorted, all remaining elements
from i to mid are also greater than arr[j]. We
immediately add (mid - i + 1) to our inversion count.
Algorithm Implementation
class Solution {
// Note: Use 'long' for return type if array size is very large.
static int inversionCount(int arr[]) {
if (arr == null || arr.length < 2) return 0;
int[] temp = new int[arr.length];
return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}
private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
int count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += mergeSortAndCount(arr, temp, left, mid);
count += mergeSortAndCount(arr, temp, mid + 1, right);
count += mergeAndCount(arr, temp, left, mid, right);
}
return count;
}
private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
int i = left; // Left subarray index
int j = mid + 1; // Right subarray index
int k = left; // Temp array index
int count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
// Core logic: arr[i] > arr[j], so all remaining
// left elements are > arr[j].
count += (mid - i + 1);
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
return count;
}
}#include <vector>
using namespace std;
class Solution {
public:
long long int inversionCount(long long arr[], long long N) {
long long temp[N];
return mergeSortAndCount(arr, temp, 0, N - 1);
}
private:
long long int mergeSortAndCount(long long arr[], long long temp[], int left, int right) {
long long int count = 0;
if (left < right) {
int mid = left + (right - left) / 2;
count += mergeSortAndCount(arr, temp, left, mid);
count += mergeSortAndCount(arr, temp, mid + 1, right);
count += mergeAndCount(arr, temp, left, mid, right);
}
return count;
}
long long int mergeAndCount(long long arr[], long long temp[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
long long int count = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i + 1);
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left; i <= right; i++) arr[i] = temp[i];
return count;
}
};class Solution:
def inversionCount(self, arr, n):
temp = [0] * n
return self._mergeSortAndCount(arr, temp, 0, n - 1)
def _mergeSortAndCount(self, arr, temp, left, right):
count = 0
if left < right:
mid = (left + right) // 2
count += self._mergeSortAndCount(arr, temp, left, mid)
count += self._mergeSortAndCount(arr, temp, mid + 1, right)
count += self._mergeAndCount(arr, temp, left, mid, right)
return count
def _mergeAndCount(self, arr, temp, left, mid, right):
i = left
j = mid + 1
k = left
count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp[k] = arr[i]
i += 1
else:
temp[k] = arr[j]
count += (mid - i + 1)
j += 1
k += 1
while i <= mid:
temp[k] = arr[i]
k += 1
i += 1
while j <= right:
temp[k] = arr[j]
k += 1
j += 1
for idx in range(left, right + 1):
arr[idx] = temp[idx]
return count