# Undestanding Recursion with return values in Merge Sort

I'm trying to solve a basic problem in Hackerearth Given an array `A` of size `N`, you need to find the number of ordered pairs `(i,j)` such that `i < j` and `A[i] > A[j]`.

I was able to find out an idea actually implemented it by having a global variable. But having a global value is not a good practice, hence I tried to pass it as parameter and I couldn't able to solve it. Am stuck with keeping an already returned value and adding an updated value to it.

``````// let ans = 0;

let mergeSort = (left, right, arr, ans) => {
let i = 0,
j = 0,
k = 0;
let leftLen = left.length,
rightLen = right.length;
while (i < leftLen && j < rightLen) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
ans += leftLen - i;
j++;
}
k++;
}
while (i < leftLen) {
arr[k] = left[i];
i++;
k++;
}
while (j < rightLen) {
arr[k] = right[j];
j++;
k++;
}
return { arr, ans };
};

let divideArray = (arr, ans) => {
if (arr.length < 2) return { arr, ans };
let N = arr.length;
let mid = Math.round(N / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, N);
ans = ans;
divideArray(left, ans);
divideArray(right, ans);
let blabla = mergeSort(left, right, arr, ans);
return blabla;
};

let merge = (arr, ans) => {
let res = divideArray(arr, ans);
return res;
};

function main(input) {
let arr = [1, 4, 3, 2, 5];
let ans = 0;
let output = merge(arr, ans);
console.log('Final', output);
}

main();
``````

In mergeSort function When the input of the left array is `[1,4]` and the right array is `[3]` the ans will be updated as `1`, also when the left array is `[1,3,4]` and right is `[2,5]` the ans will be updated as `2`. I would like to add both this ans values and return it as `3`. But somewhere am making a mistake while returning. Any help will be appreciated.

JsFiddle

EDIT:

Please note that am trying to achieve it via MergeSort and recursion i know in lot of other ways i can solve this problem for instance i have clearly mentioned i had solved it by having a global variable,which is not a good practice so please provide me a solution only via recursion and merge sort

https://codepen.io/Santhoshsanz/pen/dybedgm?editors=1112

``````    // let ans = 0;

let mergeSort = (left, right, arr, ans) => {
// console.log(left)
// console.log("*****")
// console.log(right)
// console.log("*****£££")
let i = 0,
j = 0,
k = 0;
let leftLen = left.length,
rightLen = right.length;
while (i < leftLen && j < rightLen) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
ans += leftLen - i;
j++;
}
k++;
}
while (i < leftLen) {
arr[k] = left[i];
i++;
k++;
}
while (j < rightLen) {
arr[k] = right[j];
j++;
k++;
}

return { arr, ans };
};

let divideArray = (arr, ans) => {
if (arr.length < 2) return { arr, ans };
let N = arr.length;
let mid = Math.round(N / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, N);
ans = ans;
let lans=divideArray(left, ans).ans;
let bAns=divideArray(right, ans).ans;
// console.log(bAns)
let blabla= mergeSort(left, right, arr, lans+bAns);
return blabla
};

let merge = (arr, ans) => {
let res=0+ divideArray(arr, ans).ans;
// console.log(res)
return res;
};

function main(input) {
let arr = [1,4,3,2,5];
let ans = 0;
let output = merge(arr, ans);
console.log('Final', output);
}

main();
``````

I have persisted the count val inside your divide array and used it to merge the 2 counts from the split array i.e left and right direction split

There is no need to pass an inversion count to divideArray(), it only needs to return a sub_count = left_count + right_count + merged_count. The sub_counts originate from each instance of merging and will be accumulated as recursion returns sub-counts back up the call chain to produce a total_count.

Example of an optimized top down merge sort updated to return an inversion count. A helper function (mergesort()) does a one time allocation of an auxiliary array (aux). To avoid unneeded copying of data, two mutually recursive functions are used, sortarrtoarr() sorts data from arr[] back to arr[], while sortarrtoaux() sorts data from arr[] to aux[]. Each of the mutually recursive functions calls the other in order to change the direction of merge based on the level of recursion.

``````function merge(arr, aux, bgn, mid, end) {
var i = bgn;
var j = mid;
var k = bgn;
var cnt = 0;                      // count of inversions
while(true){
if(arr[i] <= arr[j]){           // if left element <= right element
aux[k++] = arr[i++];          //   copy left element
if(i < mid)                   //   if not end of left run
continue;                   //     continue back to while
do                            //   else copy rest of right run
aux[k++] = arr[j++];        //     and break
while(j < end);
break;
} else {                        // else left element > right element
cnt += mid - i;               //   arr.slice(i,mid) is > arr[j]
aux[k++] = arr[j++];          //   copy right element
if(j < end)                   //   if not end of right run
continue;                   //     continue back to while
do                            //   else copy rest of left run
aux[k++] = arr[i++];        //     and break
while(i < mid);
break;
}
}
return cnt;                       // return inversion count
}

// sort from arr[] to aux[]
function sortarrtoaux(arr, aux, bgn, end) {
if ((end-bgn) < 2){               // if only 1 element
aux[bgn] = arr[bgn];          //   copy it to aux
return 0;                     //   return inversion count == 0
}
var cnt = 0;                      // inversion count = 0
var mid = Math.floor(bgn + (end - bgn) / 2);
cnt += sortarrtoarr(arr, aux, bgn, mid); // sort left  arr back to arr
cnt += sortarrtoarr(arr, aux, mid, end); // sort right arr back to arr
cnt += merge(arr, aux, bgn, mid, end);   // merge arr to aux
return cnt;                       // return inversion count
}

// sort from arr[] back to arr[]
function sortarrtoarr(arr, aux, bgn, end) {
if ((end-bgn) < 2)                // if only 1 element
return 0;                       //   return inversion count == 0
var cnt = 0;                      // inversion count = 0
var mid = Math.floor(bgn + (end - bgn) / 2);
cnt += sortarrtoaux(arr, aux, bgn, mid); // sort left  arr to aux
cnt += sortarrtoaux(arr, aux, mid, end); // sort right arr to aux
cnt += merge(aux, arr, bgn, mid, end);   // merge aux to arr
return cnt;                       // return inversion count
}

// entry function for mergesort
function mergesort(arr) {
if(arr.length < 2)                // if less than 2 elements
return 0;                     //   return inversion count == 0
var aux = new Array(arr.length);  // allocate aux[] and start merge sort
return sortarrtoarr(arr, aux, 0, arr.length);
}

var arr = [8, 6, 7, 5, 3, 0, 9];
var cnt = mergesort(arr);
console.log(cnt);
for (i = 1; i < arr.length; i++) {
if(arr[i-1] > arr[i]){
console.log('error');
break;
}
}``````

Scott's answer offers a functional approach. Generators, `function*` below, offer another capable and flexible way of encoding this kind of problem -

``````const descendingPairs = function* (a = [])
{ for (const i of range(0, a.length)) // for all (0 <= i < a.length)
for (const j of range(0, a.length)) // for all (0 <= i < a.length)
if (i < j) // such that i < j
if (a[i] > a[j]) // and a[i] > a[j]
yield [ a[i], a[j] ] // output descending pair
}
``````

We can optimise this by using `i` as the input for the `j` range's `start` -

``````const descendingPairs = function* (a = [])
{ for (const i of range(0, a.length)) // for all (0 < i < a.length)
for (const j of range(i + 1, a.length)) // for all (i < j < a.length)
if (a[i] > a[j]) // such that a[i] > a[j]
yield [ a[i], a[j] ] // output descending pair
}
``````

`range` is nicely-encoded using a generator as well -

``````const range = function* (start = 0, stop = 0)
{ for (let x = start; x < stop; x++)
yield x
}
``````

We can output the results of each descending pair -

``````const input =
[ 1, 4, 3, 2, 5 ]

for (const pair of descendingPairs(input))
console.log(pair)

// [ 4, 3 ]
// [ 4, 2 ]
// [ 3, 2 ]
``````

Or we can collect all pairs into an array -

``````Array.from(descendingPairs(input))
// => [ [ 4, 3 ], [ 4, 2 ], [ 3, 2 ] ]
``````

Or we can simply count them -

``````Array.from(descendingPairs(input)).length
// => 3
``````

Expand the snippet below to verify the results in your own browser -

``````const range = function* (start = 0, stop = 0)
{ for (let x = start; x < stop; x++)
yield x
}

const descendingPairs = function* (a = [])
{ for (const i of range(0, a.length))
for (const j of range(i, a.length))
if (a[i] > a[j])
yield [ a[i], a[j] ]
}

const input =
[ 1, 4, 3, 2, 5 ]

console.log(Array.from(descendingPairs(input)))
// [ [ 4, 3 ], [ 4, 2 ], [ 3, 2 ] ]

console.log(Array.from(descendingPairs(input)).length)
// 3 ``````

I'm having a hard time figuring why you are writing this with code that's all about a mergesort. It seems to me that all you need to do is to generate the index pairs where `j` > `i` (a fairly easy task) and then count those for which `A[i] > A[j]`. Recursion is a fine way (though by no means the only easy way) to create those index pairs. The rest is a `filter`/`length` combination or a `reduce`.

Here's one variation:

``````const countDescendingPairs = (xs) =>
xs .map ((x, i) => xs .slice (i + 1) .filter(y => x > y) .length)
.reduce ((a, b) => a + b, 0)

console .log (
countDescendingPairs ([8, 6, 7, 5, 3, 0, 9])
)``````

But there are many simple alternatives.

And if you wanted to retrieve those pairs, it's a straightforward modification:

``````const descendingPairs = (xs) =>
xs .flatMap (
(x, i) =>
xs .slice (i + 1)
.filter (y => x > y)
.map ((y) => ({x, y}))
)

console .log (
descendingPairs ([8, 6, 7, 5, 3, 0, 9])
)``````

Updated to add `flatMap` and to remove the incorrect indices from the second version. (You can't filter, then expect the old index to still work!)