Merge

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

            merge (A, B, C, m, n)

            {

                        pa = 1 ;     // Start index of A

                        pb = 1 ;    // Start index of B

                        pc = 1 ;    // Start index of C

                        while (pa≤ m && pb≤ n) do    // both arrays are non-empty

                        {

                        If (A[pa] < B[pb]) then

                        {

                                    C[pc] = A[pa] ;

                                    pa= pa + 1 ;

                        }

                                    else

                                    {

                                    C[pc] = B[pb] ;

                                    pb = pb + 1 ;

                        }

                                    pc = pc + 1 ;

                        }

                        while (pb ≤ n) do    // Array B is non-empty

                        {

                                    C[pc] = B[pb] ;

pb = pb + 1 ;

pc = pc + 1 ;

}

                        }