Merging means combining elements of two arrays to form a new array. The simplest way of merging two arrays is to first copy all the elements of one array into a new array and then append all the elements of the second array to the new array. If you want the resultant array to be sorted, you can sort it by any of the sorting techniques.

If the arrays are originally in sorted order, they can be merged in such a way as to ensure that the combined array is also sorted. This technique is known as merge sort.

The technique of merge sort (i.e., sorting during merging) is much more efficient than sorting after merging for arrays that are already sorted.

STEP 1: Let us consider two arrays say, A[7] and B[5] to be merged to form a new array. The new array say C will be having 7+5=12 elements.

STEP 2: Compare A[0] and B[0]; if A[0]<B[0] (say); move A[0] to C[0]. Increment the pointers of array A and array C (the pointer of that array is incremented whose element is moved in the third array).

STEP 3: Now compare the elements of A and B where the pointers are pointing. That is, compare A[1] and B[0]. Suppose that we find B[0]<A[1], so we move B[0] to C[1] and increment B’s pointer to point to the next element in array B.

C++ Implementation

.cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; }
.cl { margin: 0px; }
.cb1 { color: green; }
.cb2 { color: blue; }
.cb3 { color: maroon; }

/**
 * A and B are the input arrays which contain
 * elements in ascending order. Their respective
 * sizes are m and n. C is the output array
 * that will contain the elements from the
 * two arrays combined and in sorted order.
 */
void mergesort(int A[], int B[], int C[], int m, int n)
{
 int a=0, b=0, c=0;
 for (a=0, b=0, c=0; a<m && b<n;)
 {
 if (A[a]<B[b])
 C[c++] = A[a++];
 else
 C[c++] = B[b++];
 }
 if (a<m)
 while (a<m)
 C[c++] = A[a++];
 else
 while (b<n)
 C[c++] = B[b++];
}

Complete Program

/**
 * Merge Sort
 * http://www.byteguide.com
 */


#include <sdio.h>




void mergesort(int [], int [], int [], int, int);




int main()


{


 int A[50], B[50], C[100], m, n, i;


 printf("How many elements do you want to create the first array"


 "with? (max 50): ");


 fflush(stdout);


 scanf("%d", &m);


 puts("Enter the array elements in ascending order:");


 for (i=0; i<m; i++)


 scanf("%d", &A[i]);




 printf("nHow many elements do you want to create the second array"


 "with? (max 50): ");


 scanf("%d", &n);


 puts("Enter the array elements in ascending order:");


 for (i=0; i<n; i++)


 scanf("%d", &B[i]);


 mergesort(A, B, C, m, n);


 puts("n------The sorted array is----");


 for (i=0; i<m+n; i++)


 printf("%dn", C[i]);




 return 0;


}




/**


 * A and B are the input arrays which contain


 * elements in ascending order. Their respective


 * sizes are m and n. C is the output array


 * that will contain the elements from the


 * two arrays combined and in sorted order.


 */




void mergesort(int A[], int B[], int C[], int m, int n)


{


 int a=0, b=0, c=0;


 for (a=0, b=0, c=0; a<m && b<n;)


 {


 if (A[a]<B[b])


 C[c++] = A[a++];


 else


 C[c++] = B[b++];


 }


 if (a<m)


 while a<m)


 C[c++] = A[a++];


 else


 while (b<n)


 C[c++] = B[b++];


}


Output


How many elements do you want to create the first arraywith? (max 50): 3 Enter the array elements in ascending order: 4 8 10


How many elements do you want to create the second arraywith? (max 50): 4 Enter the array elements in ascending order: 3 5 7 9


——The sorted array is—- 3 4 5 7 8 9 10