## Assignment 7

Submission site  |  Show solution  |  Hide solution ]

In this assignment you are asked to implement merge sort on linked lists. The essential idea is described in the following figure.

We use the following type definitions. We maintain the size of a list in the list header. Maintaining the size field eliminates the need for computing the size of a list on the fly by traversing the list from the beginning to the end.

```   typedef struct _node {
int key;             /* The key value to be stored in a node */
struct _node *next;  /* Pointer to the next node */
} node;

typedef struct {
unsigned int size;   /* Number of elements in the list */
node *first;         /* Pointer to the first element in the list */
} list;
```

I provide you two functions, one for creating a random list of n elements, and the other for printing the elements in a list from beginning to end.

Part 1 [Credit: 50%]

Write a merging function that accepts two list headers as arguments, and returns a header to the merged list. The input lists are assumed to be sorted. No fresh memory allocation is to be made inside this function. Only the pointers in the input lists are to be rearranged so as to produce the merged sorted list.

```   list merge ( list L1, list L2 );
```

Part 2 [Credit: 50%]

Write a function that implements the merge sort algorithm described in the above figure. The function accepts a header to the list to be sorted. The merge sort function first breaks the list in two (almost) equal halves. The two halves are pointed to by L1 and L2. Two recursive calls are then made in order to sort the lists headed by L1 and L2. The resulting sorted sublists are merged using the merge function of Part 1. Do not make fresh memory allocation to produce the two sublists. Just break the input list in two halves by adjusting an appropriate pointer near the center of the input list.

```   list mergeSort ( list L );
```

Report the output of your program on a list of size 200.

Sample output

```Enter size of list : 40
Original list :  741 188 947 559 542 430 253 357 143 257 605 314 921 670
227 151 715 559 241 897 184 977 981 850  11 372 725 346 949 737 264 690
277 212 602 171 994 855 528 137
Sorted list   :   11 137 143 151 171 184 188 212 227 241 253 257 264 277
314 346 357 372 430 528 542 559 559 602 605 670 690 715 725 737 741 850
855 897 921 947 949 977 981 994
```

Submission site  |  Show solution  |  Hide solution ]