How to use Merge Sort In Javascript
In this approach, we recursively divide the array into smaller parts using the merge sort algorithm. During the merge step, while merging two sorted arrays, we count the reverse pairs by comparing elements from different parts. This allows us to efficiently count reverse pairs in the array.
Example: The below example uses Merge Sort to count reverse pairs using JavaScript.
let cnt = 0;
const arr = [3, 2, 4, 5, 1, 20];
function countReversePairs(arr) {
if (arr.length <= 1) {
return arr;
}
// Divide the array into two halves
const mid = Math.floor(arr.length / 2);
// Recursively sort left half
const left = countReversePairs(arr.slice(0, mid));
// Recursively sort right half
const right = countReversePairs(arr.slice(mid));
let i = 0;
let j = 0;
// Merge and count reverse pairs
while (i < left.length && j < right.length) {
if (left[i] > 2 * right[j]) {
cnt += left.length - i;
j++;
} else {
i++;
}
}
// Merge sorted left and right halves
return left.concat(right).sort((a, b) => a - b);
}
countReversePairs(arr);
console.log(cnt);
Output
3
Time Complexity: O(nlogn), where n is the number of elements in the array.
Space Complexity: O(n)
JavaScript Program to Count Reverse Pairs
Given an array, array [] of N integers, find the count of reverse pairs. A pair of indices (i, j) is said to be a reverse pair if both the following conditions are met:
0 <= i < j < Narr[i] > 2 * arr[j]
Examples:
Input: N = 6,
arr = [3, 2, 4, 5, 1, 20]
Output: 3
Explanation: The reverse pairs are:
(0, 4), arr[0] = 3 and arr[4] = 1, 3 > 2(1)
(2, 4), arr[2] = 4 and arr[4] = 1, 4 > 2(1)
(3, 4), arr[3] = 5 and arr[4] = 1, 5 > 2(1)
Input: N = 5,
arr = [2, 4, 3, 5, 1]
Output: 3
Explanation: The reverse pairs are:
(1, 4), arr[1] = 4 and arr[4] = 1, 4 > 2(1)
(2, 4), arr[2] = 3 and arr[4] = 1, 3 > 2(1)
(3, 4), arr[3] = 5 and arr[4] = 1, 5 > 2(1)
Table of Content
- Using Nested Loops
- Using Merge Sort
Contact Us