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