mergesort recursion

[Yakg]

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:

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

[Petr]

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

[doWhile]

Has anyone did it before as I'm having trouble finding it online.

Did what? Trouble finding what? What exactly is the question/problem?

[Yakg]

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.

[Yakg]

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

[doWhile]

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?

[JosAH]

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

[Yakg]

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?

[JosAH]

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

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

[JosAH]

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:

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

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

[JosAH]

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

[Yakg]

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