Originally Posted by
oogabooga
A proper merge sort does not go "all the way down". It's usual to use a sort with less overhead to sort the lists when they become "small" (small is a relative term, but maybe 10 or maybe even 100 ... other people here know more about that kind of thing).
Also, it would be nice if you could post some runnable code (complete with timing code).
Well you can test with this (for the merge sort) :
Code:
int main(void) {
struct node *head;
struct node *current;
struct node *next;
int i;
struct timeval tbegin,tend;
double texec=0.;
// Start timer
gettimeofday(&tbegin,NULL);
head = NULL;
/* insert some numbers into the list */
for (i = 100000; i > 0; i--)
head = addnode(i, head);
/* sort the list */
head = merge_sort(head);
/* print the list */
printf(" before after\n"), i = 0;
for(current = head; current != NULL; current = current->next)
printf("%4d\t%4d\n", i++, current->number);
/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);
// End timer
gettimeofday(&tend,NULL);
// Compute execution time
texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.;
printf("Elapsed time = %f\n", texec);
/* done... */
return 0;
}
And for the insert sort something like this for example :
struct node *head = NULL;
Code:
int main(void) {
struct node *current = NULL;
struct node *next = NULL;
int i = 0;
struct timeval tbegin,tend;
double texec=0.;
// Start timer
gettimeofday(&tbegin,NULL);
/* insert some numbers into the list */
for(i = 10000; i > 0; i--)
insert_node(i);
/* print the list */
printf(" before after\n"), i = 10000;
while(head->next != NULL) {
printf("%4d\t%4d\n", i--, head->number);
head = head->next;
}
/* free the list */
for(current = head; current != NULL; current = next)
next = current->next, free(current);
// End timer
gettimeofday(&tend,NULL);
// Compute execution time
texec=((double)(1000*(tend.tv_sec-tbegin.tv_sec)+((tend.tv_usec-tbegin.tv_usec)/1000)))/1000.;
printf("Elapsed time = %f\n", texec);
return 0;
}