# Thread: mergesort recursion

1. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## 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:

Java 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);
}
}```

2. Do you have a special task? Do you need make a sort algorithm?
because Java has library for this aim.

3. Moderator
Join Date
Jul 2010
Location
California
Posts
1,641
Rep Power
9
Has anyone did it before as I'm having trouble finding it online.
Did what? Trouble finding what? What exactly is the question/problem?

4. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## 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.

5. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## Forgot to mention that

no other ways are allowed and nor the use of libraries.

6. Moderator
Join Date
Jul 2010
Location
California
Posts
1,641
Rep Power
9
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?

7. 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

8. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## 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?

9. 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

10. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## 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.

11. 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:

Java 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
Last edited by JosAH; 02-20-2011 at 06:51 PM.

12. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## 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.

13. 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

14. Member
Join Date
Dec 2010
Posts
60
Rep Power
0

## Did it!!

finally I understand the principle I was completely taking this the wrong way.
Came back to read your previous reply (Jos) and got it.

This forum's members have helped me allot through my studies.
Keep up this tremendous work. :)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•