# mergesort recursion

• 02-19-2011, 03:38 PM
Yakg
mergesort recursion
hi, I am trying to combine 2 arrays into a sorted one through recursion (no loops alowed)

This is what I've written so far, it is not complete.
Has anyone did it before as I'm having trouble finding it online.

Thanks.

The code:

Code:

```public class M4{     public static int [] merge (int [] ar1,int [] ar2){         int l1 = ar1.length, l2 = ar2.length, l3 = l1+l2;         int result [] = new int [l3];         return merge(ar1,ar2,result,l1,l2,l3);     }         public static int [] merge (int [] ar1, int [] ar2, int [] result, int l1, int l2, int l3){         if (l3 == 0){             if  (ar1[0] <= ar2[0]){                 if(l2>-1)                 l2=l2-1;                  else                  result [0] =ar1[0];                 return result;             }         else{             if(l1>-1)               l1=l1-1;               else                 result [0] = ar2[0];                 return result;             }}               if (l3>l2 || l3>l1)       result =  merge (ar1,ar2,result,l1,l2,l3-1);             result = merge (ar1,ar2,result,l1-1,l2-1,l3-1);  //recursive calls                     if  (ar1[l1] <= ar2[l2]){           if(l2>0)           l2=l2-1;            else            result [l3] = ar1 [l1];           return result;         }         else{             if(l1>0)               l1=l1-1;               else               result [l3] = ar2 [l2];                 return result;             }         }         public static void main (String args[]){             int ar1[] = {2,4,6};             int ar2[] = {1,2,2};             merge(ar1,ar2);         }     }```
• 02-19-2011, 04:42 PM
Petr
Do you have a special task? Do you need make a sort algorithm?
because Java has library for this aim.
• 02-19-2011, 04:45 PM
doWhile
Quote:

Has anyone did it before as I'm having trouble finding it online.
Did what? Trouble finding what? What exactly is the question/problem?
• 02-19-2011, 04:51 PM
Yakg
basically it's
sorting two array into one.
For example if given: int a [] = {2,4,6}, int b [] = {1,2,2}.
so the result array should be: {1,2,2,2,4,6}.

Recursively without loops.

Hope it's understood this time thanks.
• 02-19-2011, 04:53 PM
Yakg
Forgot to mention that
no other ways are allowed and nor the use of libraries.
• 02-19-2011, 04:55 PM
doWhile
Quote:

sorting two array into one.
For example if given: int a [] = {2,4,6}, int b [] = {1,2,2}.
so the result array should be: {1,2,2,2,4,6}.

Recursively without loops.

Hope it's understood this time thanks.
And if you run the above (assuming it can compile because you've given us little information regarding its behavior) how does it behave?
• 02-19-2011, 05:09 PM
JosAH
Quote:

Originally Posted by Yakg
no other ways are allowed and nor the use of libraries.

First define a couple of indexes: i1, i2 and i3; a[i1] is the number to read from array a, b[i2] is the number to read from array b and result[i3] is the number to write to the result array. A few conditions need to be tested:

1) i1 == a.length && i2 == b.length: the merging is ready, return result
2) else if i1 == a.length: add b[i2] to result and call recursively with i2= i2+1
3) else if i2 == b.length add a[i1] to result and call recursively with i1= i1+1
4) else find the smallest of a[i1] and b[i2], add it to result and call recursively with i1= i1+1 or i2= i2+2

kind regards,

Jos
• 02-19-2011, 05:13 PM
Yakg
My idea was
to compare between the two arrays
so if the left array is <= the right,
than copy the number to the result array and increase
the left index and the result index by 1.
And do the opposite if left is >.

I'm trying to do this comparison, that each of the arrays position will progress only when their correspond condition is true.
What actually happens is that at the end of the recursive call they all progress together (the positions).

I think I need to control their progression individually somehow.
Does anyone know how to do this separately?
• 02-19-2011, 05:23 PM
JosAH
Quote:

Originally Posted by Yakg
I think I need to control their progression individually somehow.
Does anyone know how to do this separately?

Yup, I do, see my reply #8.

kind regards,

Jos
• 02-19-2011, 05:37 PM
Yakg
I saw it only after...Joshua
The big question is how to write it in a compiled friendly way....
I'll try to find an example as I don't want to bother to much. I'll try breaking my head working on this in the meantime.

Many thanks.
• 02-19-2011, 05:42 PM
JosAH
Quote:

Originally Posted by Yakg
The big question is how to write it in a compiled friendly way....
I'll try to find an example as I don't want to bother to much. I'll try breaking my head working on this in the meantime.

Many thanks.

You're welcome; I do the skeleton of the code for you:

Code:

```private int[] merge(int[] a, int[] b, int[] result, int i1, int i2, int i3) {   if (i1 == a.length && i2 == b.length) // step 1 in reply #8       return result;   else if (i1 == a.length) { // step 2 in reply #8       result[i3++]= b[i2++];       return merge(a, b, result, i1, i2, i3);   }   else // you do the rest ... }```
kind regards,

Jos
• 02-20-2011, 06:41 PM
Yakg
Hi, everyone I'm back again
I'll be glad if someone post the recursion mergesort code, as I think I have an idea but not enough time to practice for tomorrow's test. That will be one last big favour I need and hopefully will all go well.

Thanks.
• 02-20-2011, 06:50 PM
JosAH
Quote:

Originally Posted by Yakg
I'll be glad if someone post the recursion mergesort code, as I think I have an idea but not enough time to practice for tomorrow's test. That will be one last big favour I need and hopefully will all go well.

Thanks.

But I gave it all away in my last reply; all you have to do is complete the last two if-conditions in the same manner as I did in the first two if-conditions. Also reread my previous reply explaining what the code should do and how it should do it. I am not going to complete all your homework.

kind regards,

Jos
• 02-20-2011, 07:58 PM
Yakg
Did it!!
finally I understand the principle I was completely taking this the wrong way.