Data Structures and Algorithm_Array-4

Merging Two Arrays

Simple explanation of the Algorithm and C code to merge two arrays.

Algorithm

Input = A [ L1 … U1 ] , B[ L2 … U2 ]

Output = C[ L…U]

L = L1

U = U1 + ( U2 — L2 +1)

MERGE ( A, N1, B, N2)

Here we are trying to merge A and B to form a new array C.

1. Set i1 = L1 and set i2 = L2
2. Set L = L1
3. Set U = U1 + (U2 — L2 +1)
4. Set i = L
5. Allocate memory (size ( U - L + 1)) // this is for C array
6. Repeat steps 7and 8 while i1 < U1
7. Set C[i]= A[i1]
8. Set i = i+1 and i1 = i1 + 1 // Entire A array is transferred to C
9. Repeat steps 10 and 11 while i2 < U2
10. Set C[i] = B[i2]
11. Set i = i+1 and i2 = i2+1
12. Exit

Explanation

First assign the upper and lower limits of the two given arrays. i1 variable is assigned the lower limit of array A and i2 the lower limit of array B. Next we set the lower limit of the new array C as the lower limit of array A. Next another variable i is assigned the lower limit of array C. Next ,we are trying to figure out the space needed by the new array when merging two different arrays. This is calculated using the steps 1 through 5. Next we are assigning all the values of array A into C, making sure the array limit of A is not surpassed ( this is what the condition i1 < U1 does) . Next we assign array B to C using a similar loop.

C code

// Merge two Arrays
#include<stdio.h>
int main(){
int A[5]= {1,2,3,4,5};
int B[6]={6,7,8,9,10,11};
printf(" Array A = %d%d%d%d%d\n", A[0],A[1],A[2],A[3],A[4]);
printf(" Array B = %d%d%d%d%d%d\n", B[0],B[1],B[2],B[3],B[4],B[5]);

int C[11];
// 11 = 5 + (6-1+1)
int i = 0, i1 = 0, i2=0;
while (i1 <5)
{
    C[i]=A[i1];
    i1++;
    i++;
}
while (i2 <6 )
{
    C[i]=B[i2];
    i++;
    i2++;
}
printf(" Merged Array = %d%d%d%d%d%d%d%d%d%d%d\n", C[0],C[1],C[2],C[3],C[4],C[5],C[6],C[7],C[8],C[9],C[10], C[11]);
return 0;
}