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):

Insertion sort :Code:struct node { int number; struct node *next; };

Merge 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; } }

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; }