Page 251 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes each of size 1, and merge the first list with the second list to form a single sorted list of size 2.

Similarly we merge the third and the fourth lists to form a second single sorted list of size 2, and
so on this completes the one pass. We then consider the first sorted list of size 2 and second sorted

list of size 2, and merge them to form a single sorted list of size 4. Similarly we merge the third
and the fourth sorted lists each of size 2 to form the second single sorted list of size 4, and so on;
this completes the second pass. In the third pass we merge these adjacent sorted lists each of size

4 to form sorted lists of size 8. We continue this process till finally we end up with a single sorted
list of size n as shown in fi gure.

10 5 1 20 25 6 7 3

[5,10] [1,20] [6,25] [3,7]

[1,5,10,20] [3,6,7,25]

[1,3,5,6,7,10,20,25]

To carry out the above task, we require a procedure to merge the two sorted lists of size m and
n respectively to form a single sorted list of size (m+n), we also require a procedure to carry out

one pass of the list merging the adjacent sorted lists of the specified size. This is because we have
to carry out the repeated passes of the given list. In the first pass, we merge the adjacent lists of

size 1. In the second pass, we merge the adjacent lists of size 2, and so on. Therefore, we will call
this procedure by varying the size of the lists to be merged.
Here is a C implementation of the same.
void merge(int s[], int y[], int l, int m, int n)
{
int i,j,k;
i =1;
j = m+1;
k= 1;
while ((i <= m) && (j <= n))
{
if(x[i] <= x[j])
{

246 LOVELY PROFESSIONAL UNIVERSITY