Merging two sorted arrays into a single array

In this recipe, we will learn to merge two sorted arrays into a single array so that the resulting merged array is also in sorted form.

How to do it…

1. Let's assume there are two arrays, p and q, of a certain length. The length of the two arrays can differ. Both have some sorted elements in them, as shown in Figure 1.24:

Figure 1.24

2. The merged array that will be created from the sorted elements of the preceding two arrays will be called array r. Three subscripts or index locations will be used to point to the respective elements of the three arrays.
3. Subscript i will be used to point to the index location of array p. Subscript j will be used to point to the index location of array q and subscript k will be used to point to the index location of array r. In the beginning, all three subscripts will be initialized to 0.

4. The following three formulas will be applied to get the merged sorted array:
   1. The element at p[i] is compared with the element at q[j]. If p[i] is less than q[j], then p[i] is assigned to array r, and the indices of arrays p and r are incremented so that the following element of array p is picked up for the next comparison as follows:

r[k]=p[i];
i++;
k++

2. If q[j] is less than p[i], then q[j] is assigned to array r, and the indices of arrays q and r  are incremented so that the following element of array q is picked up for the next comparison as follows:

r[k]=q[j];
i++;
k++

3. If p[i] is equal to q[j], then both the elements are assigned to array r.  p[i] is added to r[k]. The values of the i and k indices are incremented.  q[j] is also added to r[k], and the indices of the q and r arrays are incremented. Refer to the following code snippet:

r[k]=p[i];
i++;
k++
r[k]=q[j];
i++;
k++

5. The procedure will be repeated until either of the arrays gets over. If any of the arrays is over, the remainder of the elements of the other array will be simply appended to the array r.

The mergetwosortedarrays.c program for merging two sorted arrays is as follows:

#include<stdio.h>
#define max 100

void main()
{
    int p[max], q[max], r[max];
    int m,n;
    int i,j,k;
    printf("Enter length of first array:");
    scanf("%d",&m);
    printf("Enter %d elements of the first array in sorted order     
    \n",m);
    for(i=0;i<m;i++)
        scanf("%d",&p[i]);
    printf("\nEnter length of second array:");
    scanf("%d",&n);
    printf("Enter %d elements of the second array in sorted 
    order\n",n);
    for(i=0;i<n;i++ )
        scanf("%d",&q[i]);
    i=j=k=0;
    while ((i<m) && (j <n))
    {
        if(p[i] < q[j])
        {
            r[k]=p[i];
            i++;
            k++;
        }
        else
        {
            if(q[j]< p[i])
            {
                r[k]=q[j];
                k++;
                j++;
            }
            else
            {
                r[k]=p[i];
                k++;
                i++;
                r[k]=q[j];
                k++;
                j++;
            }
        }
    }
    while(i<m)
    {
        r[k]=p[i];
        k++;
        i++;
    }
    while(j<n)
    {
        r[k]=q[j];
        k++;
        j++;
    }
    printf("\nThe combined sorted array is:\n");
    for(i = 0;i<k;i++)
        printf("%d\n",r[i]);
}

Now, let's go behind the scenes to understand the code better.

How it works...

A macro called max is defined of size 100. Three arrays, p, q, and r, are defined of size max. You will first be asked to enter the size of the first array, p, followed by the sorted elements for array p. The process is repeated for the second array q.

Three indices, i, j and k, are defined and initialized to 0. The three indices will point to the elements of the three arrays, p, q, and r, respectively.

The first elements of arrays p and q, in other words, p[0]  and q[0], are compared and the smaller one is assigned to array r.

Because q[0] is smaller than p[0], q[0] is added to array r, and the indices of arrays q and r are incremented for the next comparison as follows:

Figure 1.25

Next, p[0] will be compared with q[1]. Because p[0] is smaller than q[1], the value at p[0] will be assigned to array r at r[1]:

Figure 1.26

Then, p[1] will be compared with q[1]. Because q[1] is smaller than p[1], q[1] will be assigned to array r, and the indices of the q and r arrays will be incremented for the next comparisons (refer to the following diagram):

Figure 1.27

Let's use GCC to compile the mergetwosortedarrays.c program as follows:

D:\CBook>gcc mergetwosortedarrays.c -o mergetwosortedarrays

Now, let's run the generated executable file, mergetwosortedarrays.exe, in order to see the output of the program:

D:\CBook>./mergetwosortedarrays
Enter length of first array:4
Enter 4 elements of the first array in sorted order
4
18
56
99

Enter length of second array:5
Enter 5 elements of the second array in sorted order
1
9
80
200
220

The combined sorted array is:
1
4
9
18
56
80
99
200
220

Voilà! We've successfully merged two sorted arrays into one.