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("asdad")
  // 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!)