- 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
- 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.
- 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.
- The following three formulas will be applied to get the merged sorted array:
- 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++
- 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++
- 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++
- 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.