1. Originally Posted by iMalc
MergeSort is certainly very good for lists, better than quicksort really since that cant tend towards O(n^2).
However the killer is BucketSort. Merge Sort is a long way ahead of most other algorithms for linked-list sorting and then BucketSort is light-years ahead of that.
The catch of course is that your key needs to support being split into buckets, as well as just being directly comparable. In your case you are using ints for which it is fine.

Regards.

2. Originally Posted by evariste

Regards.
Bucket sort is just a sort where you separate the data into buckets, sort the buckets, and then rebuild a new sorted data structure. One example is here.

3. Originally Posted by whiteflags
Bucket sort is just a sort where you separate the data into buckets, sort the buckets, and then rebuild a new sorted data structure. One example is here.
Tnakyou very much whiteflags .

Regards.

4. Originally Posted by manasij7479
Insertion sort is O(n^2) only when each insertion is linear.
That is generally not the case in lists. (I'm not very sure about this point, especially in this context)
Insertion sort on an array has O(n^2) time complexity because the insertion takes linear time even though finding the insertion point can be done in O(log n) time. Insertion sort on a linked list would still have O(n^2) time complexity because while the insertion takes constant time, finding the insertion point takes linear time.

5. Hello again,

I do some tests and i don't undersrand the results, i used the merge sort algorithm described here :

And compared it to an insertion sort algorithm :

merge sort algorithm :

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define FALSE 0
#define TRUE 1

struct element {
struct element *next, *prev;
int i;
};

int cmp(struct element *a, struct element *b) {
return a->i - b->i;
}

struct element* listsort(struct element *list) {
struct element  *p, *q, *e, *tail, *oldhead;
int insize, nmerges, psize, qsize, i;

/*
* Silly special case: if `list' was passed in as NULL, return
* NULL immediately.
*/
if (!list)
return NULL;

insize = 1;
while (1) {
p = list;
list = NULL;
tail = NULL;

nmerges = 0;  /* count number of merges we do in this pass */
while (p) {
nmerges++;  /* there exists a merge to be done */
/* step `insize' places along from p */
q = p;
psize = 0;
for (i = 0; i < insize; i++) {
psize++;
q = q->next;
if (!q) break;
}
/* if q hasn't fallen off end, we have two lists to merge */
qsize = insize;

/* now we have two lists; merge them */
while (psize > 0 || (qsize > 0 && q)) {
if (psize == 0) {
/* p is empty; e must come from q. */
e = q; q = q->next; qsize--;
} else if (qsize == 0 || !q) {
/* q is empty; e must come from p. */
e = p; p = p->next; psize--;
} else if (cmp(p,q) <= 0) {
/* First element of p is lower (or same);
* e must come from p. */
e = p; p = p->next; psize--;
} else {
/* First element of q is lower; e must come from q. */
e = q; q = q->next; qsize--;
}

/* add the next element to the merged list */
if (tail) {
tail->next = e;
} else {
list = e;
}

tail = e;

}
/* now p has stepped `insize' places along, and q has too */
p = q;
}
tail->next = NULL;

/* If we have done only one merge, we're finished. */
if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
return list;

/* Otherwise repeat, merging lists twice the size */
insize *= 2;

}
}

struct element *addnode(int number, struct element *next)
{
struct element *tnode;

tnode = (struct element*)malloc(sizeof(struct element));

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

return tnode;
}

int main(void) {
struct element *current;
struct element *next;
int j;
struct timeval tbegin,tend;
double texec=0.;

// Start timer
gettimeofday(&tbegin,NULL);

/* insert some numbers into the linked list */
for (j = 1000001; j >= 0; j--)

/* print the list */
printf(" before after\n"), j = 1000001;
for(current = head; current != NULL; current = current->next)
printf("%4d\t%4d\n", j--, current->i);

/* 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;
}```
The insertion sort code :

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

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

/* insert a node directly at the right place in the linked list */
void insert_node(int value);

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 linked list */
for(i = 100001; i >= 0 ; i--)
insert_node(i);

/* print the list */
printf(" before  after\n"), i = 100001;
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);

return 0;
}

void insert_node(int value) {
struct node *new_node = NULL;
struct node *cur_node = NULL;
struct node *last_node = NULL;
int found;

new_node = (struct node *)malloc(sizeof(struct node ));
if(new_node == NULL) {
printf("memory problem\n");
}
new_node->number = value;
/* If the first element */
new_node->next = NULL;
new_node->prev = NULL;
}

else if (new_node->number < head->number) {
new_node->prev = NULL;
}

else {
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;
}
}
if( found == 1 )
{
new_node->prev = cur_node->prev;
new_node->next = cur_node;
cur_node->prev->next = new_node;
cur_node->prev = new_node;
}
else
{
last_node->next = new_node;
new_node->next = NULL;
new_node->prev = last_node;
}
}

}```
and on my machine :

Code:
```./insertion_sort
Elapsed time = 0.940000
./merge_sort
Elapsed time = 9.445000```
Can someone explain to me this results thanks.

Regards.

6. When testing merge sort, you insert 1000002 elements into the linked list; when testing with insertion sort, you insert 100002 elements into the linked list.

7. Originally Posted by laserlight
When testing merge sort, you insert 1000002 elements into the linked list; when testing with insertion sort, you insert 100002 elements into the linked list.
Really thanks laserlight , apologize.

Many regards.