Sorting list performances

Hi all,

I have a list that contain about (200000 elements) and i want to keep them in a sorting order, so i do some testing with insertion sort and merge sort but it seems that insertion sort is better!! is it normal? how can i improve time and CPU performances? Thanks for your help.

My node (for simplicity, i omitted the prev node in the node struct):

Code:

`struct node {`

int number;

struct node *next;

};

Insertion sort :

Code:

`void insert_node(int value) {`

struct node *new_node = NULL;

struct node *cur_node = NULL;

struct node *last_node = NULL;

int found; /* 1 means found a place to insert the new node in, 0 means not*/

new_node = (struct node *)malloc(sizeof(struct node *));

if(new_node == NULL) {

printf("memory problem\n");

}

new_node->number = value;

/* If the first element */

if (head == NULL) {

new_node->next = NULL;

head = new_node;

}

else if (new_node->number < head->number) {

new_node->next = head;

head = new_node;

}

else {

cur_node = head;

found = 0;

while (( cur_node != NULL ) && ( found == 0 )) {

if( new_node->number < cur_node->number )

{

found = 1;

}

else

{

last_node = cur_node;

cur_node = cur_node->next;

}

}

/* We got the right place to insert our node */

if( found == 1 )

{

new_node->next = cur_node;

}

/* Insert at the tail of the list */

else

{

last_node->next = new_node;

new_node->next = NULL;

}

}

Merge Sort :

Code:

`/* 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 *merge_sort(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(merge_sort(head_one), merge_sort(head_two));

}

/* 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;

}