Page 255 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes θ(n log n) is a lower bound for the problem of external-memory sorting. That is, multiway merge
m
sort is an asymptotically optimal algorithm.

12.6 Merging of two Sorted Lists

Assume that two lists to be merged are sorted in descending order. Compare the first element of

the first list with the first element of the second list. If the element of the first list is greater, then
place it in the resultant list. Advance the index of the first list and the index of the resultant list

so that they will point to the next term. If the element of the first list is smaller, place the element
of the second list in the resultant list. Advance the index of the second list and the index of the
resultant list so that they will point to the next term.
Repeat this process until all the elements of either the first list or the second list are compared. If

some elements remain to be compared in the first list or in the second list, place those elements in

the resultant list and advance the corresponding index of that list and the index of the resultant
list.

Suppose the first list is 10 20 25 50 63, and the second list is 12 16 62 68 80. The sorted lists are 63
50 25 20 10 and 80 68 62 16 12.

The first element of the first list is 63, which is smaller than 80, so the first element of the resultant

list is 80. Now, 63 is compared with 68; again it is smaller, so the second element in the resultant
list is 68. Next, 63 is compared with 50. In this case it is greater, so the third element of the
resultant list is 63.
Repeat this process for all the elements of the first list and the second list. The resultant list is 80

68 63 62 50 25 20 16 12 10.

Lab Exercise Program:
#include<stdio.h>
#include<conio.h>
void main()
{
void read(int *,int);
void dis(int *,int);
void sort(int *,int);
void merge(int *,int *,int *,int);
int a[5],b[5],c[10];
clrscr();
printf(“Enter the elements of first list \n”);
read(a,5); /*read the list*/
printf(“The elements of first list are \n”);
dis(a,5); /*Display the first list*/
printf(“Enter the elements of second list \n”);
read(b,5); /*read the list*/
printf(“The elements of second list are \n”);
dis(b,5); /*Display the second list*/

250 LOVELY PROFESSIONAL UNIVERSITY