Merge
Merging
is a process of combining two or more sorted arrays into a single sorted array.
Explanation
Suppose
A[m] and B[n] are two sorted arrays. Merging is a process of combining these
two arrays into a single sorted array C[m+n]. Steps to be followed are
i)
Scan both arrays left to right
ii)
Compare A[1] with B[1]. If A[1] is less
than B[1] put A[1] as C[1] and compare A[2] with B[1] and so on, else put B[1]
as C[1] and compare A[1] with B[2] and so on.
iii)
Repeat step ii until any one array
becomes empty.
iv)
If A array becomes empty, store all the
remaining B array elements in the same order in the C array. Besides store all
the remaining A array elements in the same order in the B array.
Procedure
