1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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);
}
|
