Count Inversions in an Array Using Merge Sort | Java | Divide & Conquer

Lecture Resources
https://github.com/Tiwarishashwat/Java-Plus-DSA-Placement-Course/tree/main/Lecture-106%20-%20Count%20Inversion

In this lecture, we solve the Inversion Count problem using a Merge Sort–based approach, which reduces the time complexity from brute force O(n²) to an efficient O(n log n).

🔍 Problem Statement

Given an array arr[], an inversion is a pair (i, j) such that:

i is less than j

arr[i] is greater than arr[j]

Your task is to count the total number of inversions in the array.

🧠 Key Insight

A simple nested loop solution works but is too slow for large inputs.

Using Divide and Conquer, we count inversions while merging two sorted halves.

When an element from the right half is placed before an element from the left half, it forms multiple inversions at once.

⚙️ Approach (Merge Sort Based)
1️⃣ Divide

Recursively split the array into two halves until single elements remain.

2️⃣ Conquer (Merge Step)

Merge two sorted halves.

If a1[i] is greater than a2[j], then:

inversions += (remaining elements in left half)
= (n1 - i)

3️⃣ Combine

Sum inversions from:

Left half

Right half

Merge step

Why This Problem is Important

✔ Very common in FAANG & GFG interviews
✔ Tests understanding of Merge Sort internals
✔ Builds foundation for:

Counting smaller elements after self

Array disorder metrics

Advanced divide-and-conquer techniques
Timestamp:
0:00 - Count Inversion
7:36 - Code
10:33 - Outro

Видео Count Inversions in an Array Using Merge Sort | Java | Divide & Conquer канала ShashCode