flac: Saner EOF handling
[cmus.git] / mergesort.c
blob0e947152bb2913327c977009e8d6a5ace5cd3c2e
1 #include "mergesort.h"
2 #include "list.h"
4 void list_mergesort(struct list_head *head,
5 int (*compare)(const struct list_head *, const struct list_head *))
7 LIST_HEAD(empty);
8 struct list_head *unsorted_head, *sorted_head, *p, *q, *tmp;
9 int psize, qsize, K, count;
11 if (list_empty(head))
12 return;
14 unsorted_head = head;
15 sorted_head = ∅
16 K = 1;
17 while (1) {
18 p = unsorted_head->next;
19 count = 0;
20 do {
21 q = p;
22 psize = 0;
23 while (psize < K) {
24 if (q == unsorted_head)
25 break;
26 psize++;
27 q = q->next;
29 qsize = K;
30 while (1) {
31 struct list_head *e;
33 if (q == unsorted_head)
34 qsize = 0;
35 if (psize == 0 && qsize == 0)
36 break;
37 if (!psize || (qsize && compare(p, q) > 0)) {
38 e = q;
39 q = q->next;
40 qsize--;
41 } else {
42 e = p;
43 p = p->next;
44 psize--;
46 list_del(e);
47 list_add_tail(e, sorted_head);
49 count++;
50 p = q;
51 } while (p != unsorted_head);
53 if (count == 1) {
54 head->next = sorted_head->next;
55 head->prev = sorted_head->prev;
56 sorted_head->prev->next = head;
57 sorted_head->next->prev = head;
58 return;
60 tmp = unsorted_head;
61 unsorted_head = sorted_head;
62 sorted_head = tmp;
63 K *= 2;