1. Count Inversions

Problem Statement

Count the number of inversions in an array. An inversion is a pair of indices (i, j) such that i < j and arr[i] > arr[j].

Pattern Used

Divide and Conquer / Merge Sort

Approach (High-level)

• Method 1 (Brute Force): Use nested loops to check all pairs (i, j) where i < j and count when arr[i] > arr[j]
  • Issue: Runtime error on large inputs due to O(n²) complexity
• Method 2 (Merge Sort - Optimal): Modify merge sort to count inversions during merge step
  • During merge, when element from right half is smaller and picked, it forms inversions with all remaining elements in left half
  • Count inversions as mid - i + 1 when arr[j] is picked before arr[i]
  • Recursively count inversions in left half, right half, and during merge

Time & Space Complexity

• Brute Force:
  • Time: O(n²)
  • Space: O(1)
• Merge Sort:
  • Time: O(n log n)
  • Space: O(n) for temporary array

GFG : Count Inversions

https://www.geeksforgeeks.org/problems/inversion-of-array-1587115620/1

//Method 1: But RunTIme error
class Solution {
public:
    int inversionCount(vector<int> &arr) {
        int count = 0;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                count = arr[i] > arr[j] ? count + 1 : count;
            }
        }
        return count;
    }
};

//Merge Sort -> o(n log n)
class Solution {
public:
    long long merge(vector<int>& arr, vector<int>& temp, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int k = start;
        long long c = 0;

        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
              //case: count inversion case
                temp[k++] = arr[j++];
                c += (mid - i + 1);  // count inversions
            }
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= end) {
            temp[k++] = arr[j++];
        }

        for (int idx = start; idx <= end; idx++) {
            arr[idx] = temp[idx];
        }

        return c;
    }

    long long mergeSort(vector<int>& arr, vector<int>& temp, int start, int end) {
        if (start >= end) return 0;

        long long c = 0;
        int mid = start + (end - start) / 2;

        c += mergeSort(arr, temp, start, mid);
        c += mergeSort(arr, temp, mid + 1, end);
        c += merge(arr, temp, start, mid, end);

        return c;
    }

    long long inversionCount(vector<int>& arr) {
        vector<int> temp(arr.size(), 0);
        return mergeSort(arr, temp, 0, arr.size() - 1);
    }
};

2. In-Place Merge Sort

Problem Statement

Sort an array using merge sort with different implementation strategies including in-place merging.

Pattern Used

Divide and Conquer / Merge Sort Variants