CODEWITHSUNDEEP
javaarrayssortingmerge
Regexes
Regexes

Reputation: 105

2 way merge in java if arrays have elements with repetition

So I have been trying to merge 2 pre-sorted arrays and make it into 1 sorted array. Now the presorted arrays have elements with repetition. Here is what i have 

public class TwoWayMerge {
    public void merge(int[]a,int m,int[]b,int n)
    {
        //a=50,50,50,87,88
        //b=10,20,50,89,89,120
        //m=5 length of a
        //n=6 length of b
        //c is new array
        int i=0,j=0,k=0;
        int[]c=new int[m+n];
        while(i<m && j<n && k<m+n )
        {
            if(i<m && j<n && k<m+n && a[i]<=b[j])
            {
                c[k]=a[i];
                i=i+1;
            }
            if(i<m && j<n && k<m+n && b[j]<=a[i])
            {
                c[k]=b[j];
                j=j+1;
            }
            k=k+1;
        }


        if(i==m-1)
        {
            while(j<n && k<m+n )
            {
                c[k]=b[j];
                k++;
                j++;
            }
        }
        if(j==n-1)
        {
            while(i<m && k<m+n)
            {
                c[k]=a[i];
                k++;
                i++;
            }

        }
        for(i=0;i<m+n;i++)
        {
            System.out.print(c[i]+" ");
        }

    }

    public static void main(String[] args) {

        TwoWayMerge obj=new TwoWayMerge();
        int[] a= {50,50,50,87,88};//i4
        int[] b= {10,20,50,89,89,120};//j5
        obj.merge(a,5,b,6);

    }

}

Now in this step

a[i]<=b[j]
b[j]<=a[i]

will be executed twice and i got only 3 "50"s instead of 4 coz we have common elements in two arrays that too with repetitions.

My output

10 20 50 50 50 87 88  0 0 0

Expected output

10 20 50 50 50 50 87 88 89 89 120

Stuck here, need suggestions.

Thanks for reading.

Upvotes: 1

Views: 118

Answers (1)

Harshal Parekh
Harshal Parekh

Reputation: 6017

In your code, you reached the end of array a and your loop terminated.

int[] a = {50, 50, 50, 87, 88};
int[] b = {10, 20, 50, 89, 89, 120};
int m = 5;
int n = 6;
int i = 0, j = 0, k;
int[] c = new int[m + n];

for (k = 0; k < m + n && i < m && j < n; k++) {
    if (a[i] <= b[j]) {
        c[k] = a[i++];
    } else {
        c[k] = b[j++];
    }
}
for (; i < m; i++) {
    c[k++] = a[i];
}
for (; j < n; j++) {
    c[k++] = b[j];
}
System.out.println(Arrays.toString(c));
// [10, 20, 50, 50, 50, 50, 87, 88, 89, 89, 120]

You need two extra loops, iterating on remaining elements of a or b, if any.

Side note:

if(i<m && j<n && k<m+n && a[i]<=b[j])

No need to go over the loop condition again here. You can simplify it as:

if (a[i] <= b[j])

After your edit, I can see that your problem is very simple:

if(j==n-1)

Here, what if j is at the first position?

Example

a = {1, 2, 3, 4, 5};
b = {6, 7, 8, 9};

Your j will be 0. You need to change the same condition to:

if (j <= n - 1)

Similarly for i.

Upvotes: 1

Related Questions