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
83
|
/*
* Copyright 2008-2013 Various Authors
* Copyright 2004 Timo Hirvonen
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, see <http://www.gnu.org/licenses/>.
*/
#include "mergesort.h"
#include "list.h"
void list_mergesort(struct list_head *head,
int (*compare)(const struct list_head *, const struct list_head *))
{
LIST_HEAD(empty);
struct list_head *unsorted_head, *sorted_head, *p, *q, *tmp;
int psize, qsize, K, count;
if (list_empty(head))
return;
unsorted_head = head;
sorted_head = ∅
K = 1;
while (1) {
p = unsorted_head->next;
count = 0;
do {
q = p;
psize = 0;
while (psize < K) {
if (q == unsorted_head)
break;
psize++;
q = q->next;
}
qsize = K;
while (1) {
struct list_head *e;
if (q == unsorted_head)
qsize = 0;
if (psize == 0 && qsize == 0)
break;
if (!psize || (qsize && compare(p, q) > 0)) {
e = q;
q = q->next;
qsize--;
} else {
e = p;
p = p->next;
psize--;
}
list_del(e);
list_add_tail(e, sorted_head);
}
count++;
p = q;
} while (p != unsorted_head);
if (count == 1) {
head->next = sorted_head->next;
head->prev = sorted_head->prev;
sorted_head->prev->next = head;
sorted_head->next->prev = head;
return;
}
tmp = unsorted_head;
unsorted_head = sorted_head;
sorted_head = tmp;
K *= 2;
}
}
|