Results 1 to 14 of 14
Thread: mergesort recursion
 02192011, 03:38 PM #1Member
 Join Date
 Dec 2010
 Posts
 59
 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=l21; else result [0] =ar1[0]; return result; } else{ if(l1>1) l1=l11; else result [0] = ar2[0]; return result; }} if (l3>l2  l3>l1) result = merge (ar1,ar2,result,l1,l2,l31); result = merge (ar1,ar2,result,l11,l21,l31); //recursive calls if (ar1[l1] <= ar2[l2]){ if(l2>0) l2=l21; else result [l3] = ar1 [l1]; return result; } else{ if(l1>0) l1=l11; 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); } }
 02192011, 04:42 PM #2
Do you have a special task? Do you need make a sort algorithm?
because Java has library for this aim.Skype: petrarsentev
http://TrackStudio.com
 02192011, 04:45 PM #3Moderator
 Join Date
 Jul 2010
 Location
 California
 Posts
 1,641
 Rep Power
 7
Has anyone did it before as I'm having trouble finding it online.
 02192011, 04:51 PM #4Member
 Join Date
 Dec 2010
 Posts
 59
 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.
 02192011, 04:53 PM #5Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
Forgot to mention that
no other ways are allowed and nor the use of libraries.
 02192011, 04:55 PM #6Moderator
 Join Date
 Jul 2010
 Location
 California
 Posts
 1,641
 Rep Power
 7
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.
 02192011, 05:09 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,904
 Blog Entries
 7
 Rep Power
 22
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,
Joscenosillicaphobia: the fear for an empty beer glass
 02192011, 05:13 PM #8Member
 Join Date
 Dec 2010
 Posts
 59
 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?
 02192011, 05:23 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,904
 Blog Entries
 7
 Rep Power
 22
 02192011, 05:37 PM #10Member
 Join Date
 Dec 2010
 Posts
 59
 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.
 02192011, 05:42 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,904
 Blog Entries
 7
 Rep Power
 22
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 ... }
JosLast edited by JosAH; 02202011 at 06:51 PM.
cenosillicaphobia: the fear for an empty beer glass
 02202011, 06:41 PM #12Member
 Join Date
 Dec 2010
 Posts
 59
 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.
 02202011, 06:50 PM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,904
 Blog Entries
 7
 Rep Power
 22
But I gave it all away in my last reply; all you have to do is complete the last two ifconditions in the same manner as I did in the first two ifconditions. 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,
Joscenosillicaphobia: the fear for an empty beer glass
 02202011, 07:58 PM #14Member
 Join Date
 Dec 2010
 Posts
 59
 Rep Power
 0
Similar Threads

help with mergesort
By desconocido in forum New To JavaReplies: 5Last Post: 09152010, 03:56 AM 
recursion and tailrecursion differences
By OptimusPrime in forum New To JavaReplies: 2Last Post: 12282009, 07:26 PM 
mergeSort
By Blue_beaver in forum New To JavaReplies: 2Last Post: 10112009, 10:55 PM 
Recursion
By jachandru in forum New To JavaReplies: 1Last Post: 01242009, 01:52 PM 
Recursion
By Mika in forum New To JavaReplies: 5Last Post: 01042009, 02:13 AM
Bookmarks