Counting Inversions is a technique used in computer science and mathematics to count the number of pairs in an array or a list of elements that are out of order. The technique is widely used in various algorithms and data structures, including sorting algorithms, such as the Merge Sort algorithm. In this article, we will discuss the implementation of the Count Inversion - Merge Sort algorithm in C++.
The Merge Sort algorithm is a well-known sorting algorithm that is based on the divide-and-conquer strategy. The algorithm divides the array or list of elements into two equal halves, recursively sorts each half, and then merges the two sorted halves to produce a final sorted array. The time complexity of the Merge Sort algorithm is O(n log n), making it a highly efficient algorithm for sorting large datasets.
To implement the Count Inversion - Merge Sort algorithm in C++, we will start by defining a function that takes an array or a list of elements as its input and returns the number of inversions. The function will begin by dividing the array or list of elements into two equal halves, recursively calling itself to sort each half. Once both halves are sorted, the function will merge the two halves and count the number of inversions as it does so.
int mergeSort(int arr[], int n) {
if (n < 2)
return 0;
int mid = n / 2;
int left[mid];
int right[n - mid];
for (int i = 0; i < mid; i++)
left[i] = arr[i];
for (int i = mid; i < n; i++)
right[i - mid] = arr[i];
int inv_count = mergeSort(left, mid) + mergeSort(right, n - mid);
int i = 0, j = 0, k = 0;
while (i < mid && j < n - mid) {
if (left[i] <= right[j])
arr[k++] = left[i++];
else {
inv_count += (mid - i);
arr[k++] = right[j++];
}
}
while (i < mid)
arr[k++] = left[i++];
while (j < n - mid)
arr[k++] = right[j++];
return inv_count;
}
In this function, we first check if the size of the array or list of elements is less than two. If it is, we return 0 since there are no inversions in an array or list of size less than two. Next, we divide the array or list of elements into two equal halves, and create two arrays, left and right, to store each half. We then recursively call the mergeSort function for each half, and add the number of inversions from each half to the inv_count variable.
Once both halves are sorted, we merge the two halves, and as we do so, we count the number of inversions. We do this by comparing the elements of the left and right arrays, and if the element in the left array is greater than the element in the right array, we increment the inv_count variable by the number of elements remaining in the left array.
After the two halves are merged, we return the number of inversions, which is stored in the inv_count variable.
To test our implementation of the Count Inversion -
