diff options
Diffstat (limited to 'list_sort.c')
-rw-r--r-- | list_sort.c | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/list_sort.c b/list_sort.c new file mode 100644 index 0000000..6c6f54c --- /dev/null +++ b/list_sort.c @@ -0,0 +1,82 @@ +/* + * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc. + * See COPYING file for license information + */ + +#include <stdio.h> +#include <stdlib.h> +#include "list_sort.h" + +void list_sort(struct list_head * list, int (*node_compare)(struct list_head *, struct list_head *)) +{ + struct list_head *p, *q, *t; + struct list_head tmp; + int merges = 0; + int k = 1; + int psize, qsize; + + if (list_empty(list)) + return; + + do + { + INIT_LIST_HEAD(&tmp); + p = list->next; + merges = 0; + psize = qsize = 0; + + while (p != list) + { + merges++; + q = p; + + while (q != list && psize < k) + { + q = q->next; + psize++; + } + + qsize = k; + + while (psize || (qsize && q != list)) + { + if (psize && (qsize == 0 || q == list || node_compare(p, q) <= 0)) + { + t = p; + p = p->next; + psize--; + } + else if (qsize == 0) + { + printf("whoaa. qsize is zero\n"); + exit (1); + } + else + { + t = q; + q = q->next; + qsize--; + } + + list_del(t); + + list_add(t, tmp.prev); + } + + p = q; + } + + if (!list_empty(list)) + { + printf("whoaa. initial list not empty\n"); + exit (1); + } + + list_splice(&tmp, list); + k *= 2; + + //printf("done w sort pass %d %d\n", k, merges); + } + while (merges > 1); +} + |