> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/count-inversions-in-an-array.md).

# Count Inversions in an array

*Inversion Count* for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.\
Formally speaking, two elements a\[i] and a\[j] form an inversion if a\[i] > a\[j] and i < j

**Example:**

```
Input: arr[] = {8, 4, 2, 1}
Output: 6

Explanation: Given array has six inversions:
(8,4), (4,2),(8,2), (8,1), (4,1), (2,1).


Input: arr[] = {3, 1, 2}
Output: 2

Explanation: Given array has two inversions:
(3, 1), (3, 2) 
```

```java
class GFG {
    // Some Question
    // Why this works ?
    // 1) When we are merging the sorted parts, then we have already taken care of
    // inversions within each part, therefore we only need to take care of
    // inversions with the other part
    // 2) We need to understand that when we compare i & j in sorted order, you
    // might think that we need inversion in unsorted array
    // But remember that 1st part is sorted within itself that means that value at
    // index i, will be before j value in the original array aswell
    public static long merge(int[] arr, int start, int end) {
        int mid = start + (end - start) / 2;
        int[] holderArr = new int[end - start + 1];
        int pointer1 = start, pointer2 = mid + 1, index = 0;
        long inversions = 0;
        while (pointer1 <= mid && pointer2 <= end) {
            if (arr[pointer1] <= arr[pointer2])
                holderArr[index++] = arr[pointer1++];
            // If arr[i] > arr[j], then all the elements will be > arr[j]
            // because it is sorted array
            else {
                inversions += (mid - pointer1 + 1);
                holderArr[index++] = arr[pointer2++];
            }
        }
        while (pointer1 <= mid)
            holderArr[index++] = arr[pointer1++];
        while (pointer2 <= end)
            holderArr[index++] = arr[pointer2++];
        // Copying the changes into original array
        for (int i = start; i <= end; i++)
            arr[i] = holderArr[i - start];
        return inversions;
    }

    public static long mergeSort(int[] arr, int start, int end) {
        if (start >= end)
            return 0L;
        int mid = start + (end - start) / 2;
        long leftInversions = mergeSort(arr, start, mid);
        long rightInversions = mergeSort(arr, mid + 1, end);

        return leftInversions + rightInversions + merge(arr, start, end);
    }

    public static long countInversions(int[] arr) {
        return mergeSort(arr, 0, arr.length - 1);
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/count-inversions-in-an-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.