How to Merge two sorted arrays in O(n) time

Assume that we have two sorted arrays and we want to merge both the arrays efficiently into a single sorted array.

The algorithm we are going to use is - kind of DB sort merge Join algorithm.

While joining 2 tables in DB, DB sorts both the tables first and compare against the join columns.

For example, If we have two tables, Table A and Table B.

For simplicity, let us take only two columns.

empid	name
1	AAA
2	BBB
3	CCC
4	DDD
5	EEE
6	FFF

empid	ADDRESS
2	AAA
4	BBB
6	CCC

If we want to join these two tables using empid, then one among the DB join algorithm is Merge Join algorithm.

DB sorts these two tables using the join columns, In this case it would be empid.

It compares table 1 and table 2's empid.
Initially we start iterating each row, If the value of first table <  value of second table, then we ignore this row, Then we will iterate the next row only from first table.
Now we compare second row's value of first table against the first row value of second table, Bot matches it outputs this row.
Next we start iterating third row, Now if the value of first table > value of second table then we will start iterating from second table and continue the comparision.

In general, Initially we start with both the tables, After the comparison we will decide which table we want to iterate next, If left table value is smaller then we will iterate left table, If the right table value is small, we will iterate the right table. It continues until one among the table is iterated completely.


===============================================

The same principle applies to merge the sorted rows into a single sorted row.

Assume that we have the following arrays.

A = {1, 4, 6, 8, 10 }
B = { 2, 3, 5, 9 }


Now we want to merge these two arrays.

We start iterating both the arrays with two different variables, i and j refers to A and B.
Create an empty array with the length of (sum(Length A, Length B)).

If i < j then
start iterating values from B, add i to the new array then increment i.
else
start iterating values from B, add j to the new array then increment j.
Continue the iteration until i<A.length or j<B.length.

Now do the individual iterations of A and B seperately.
A:
Iterate until i<A.length.
    Get the element and add it to new Array.
B:

Iterate until j<B.length.
    Get the element and add it to new Array.

The Java code for this algorithm is given below.

In the example mentioned above, the first while loop would iterate for 8 times, second while loop iterate for 1 time, third for none, because of Length of B < Length of A.

The below code would complete the operation in O(n).



private static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length+b.length];
        int i=0, j=0;
        int k=0;
   
        while(i<a.length && j<b.length) {
            if(a[i]<=b[j]) {
                c[k] = a[i];
                i++;
            } else {
                c[k] = b[j];
                j++;
            }
            k=k+1;
        }
   
        while(i<a.length) {
            c[k] = a[i];
            i++;
            k=k+1;
        }

        while(j<b.length) {
            c[k] = b[j];
            j++;
            k=k+1;
        
        }
        System.out.println(k+"**********");
        return c;
    }