### Simple Merge Sort Program in C

``` <!-- google_ad_client="pub-1880930424339742"; google_ad_host="pub-6693688277674466"; google_ad_width=336; google_ad_height=280; google_ad_format="336x280_as"; google_ad_type="text_image"; google_color_border="FFFFFF"; google_color_bg="FFFFFF"; google_color_link="000000"; google_color_url="0033CC"; google_color_text="444444"; //--> Merge sort [linked list]```

`#include <stdio.h>`
`#include <stdlib.h>`

`struct node {`
` int number;`
` struct node *next;`
`};`

`/* add a node to the linked list */`
`struct node *addnode(int number, struct node *next);`
`/* preform merge sort on the linked list */`
`struct node *mergesort(struct node *head);`
`/* merge the lists.. */`
`struct node *merge(struct node *head_one, struct node *head_two);`

`int main(void) {`
` struct node *head;`
` struct node *current;`
` struct node *next;`
` int test[] = {8, 3, 2, 6, 1, 5, 4, 7, 9, 0};`
` int i;`

` head = NULL;`
` /* insert some numbers into the linked list */`
` for(i = 0; i < 10; i++)`
`  head = addnode(test[i], head);`

` /* sort the list */`
` head = mergesort(head);`

` /* print the list */`
` printf(" before  after\n"), i = 0;`
` for(current = head; current != NULL; current = current->next)`
`  printf("%4d\t%4d\n", test[i++], current->number);`

` /* free the list */`
` for(current = head; current != NULL; current = next)`
`  next = current->next, free(current);`

` /* done... */`
` return 0;`
`}`

`/* add a node to the linked list */`
`struct node *addnode(int number, struct node *next) {`
` struct node *tnode;`

` tnode = (struct node*)malloc(sizeof(*tnode));`

` if(tnode != NULL) {`
`  tnode->number = number;`
`  tnode->next = next;`
` }`

` return tnode;`
`}`

`/* preform merge sort on the linked list */`
`struct node *mergesort(struct node *head) {`
` struct node *head_one;`
` struct node *head_two;`

` if((head == NULL) || (head->next == NULL)) `
`  return head;`

` head_one = head;`
` head_two = head->next;`
` while((head_two != NULL) && (head_two->next != NULL)) {`
`  head = head->next;`
`  head_two = head->next->next;`
` }`
` head_two = head->next;`
` head->next = NULL;`

` return merge(mergesort(head_one), mergesort(head_two));`
`}`

``` <!-- google_ad_client="pub-1880930424339742"; google_ad_host="pub-6693688277674466"; google_ad_width=200; google_ad_height=90; google_ad_format="200x90_0ads_al_s"; google_color_border="FFFFFF"; google_color_bg="FFFFFF"; google_color_link="000000"; google_color_url="0033CC"; google_color_text="444444"; //--> /* merge the lists.. */```
`struct node *merge(struct node *head_one, struct node *head_two) {`
` struct node *head_three;`

` if(head_one == NULL) `
`  return head_two;`

` if(head_two == NULL) `
`  return head_one;`

` if(head_one->number < head_two->number) {`
`  head_three = head_one;`
`  head_three->next = merge(head_one->next, head_two);`
` } else {`
`  head_three = head_two;`
`  head_three->next = merge(head_one, head_two->next);`
` }`

` return head_three;`
`}`