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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#include <math.h>
#include <stddef.h>
#include "sorters.h"
#include "common.h"
struct array {
char *base;
size_t nmel;
};
/* buf must be large enough to hold as->nmel elements */
static void merge_blocks(char *buf, struct array *as, size_t bs_nmel, size_t width, cmpfun cmp)
{
char *a = buf;
char *b = as->base + as->nmel * width;
char *target = as->base;
swap(a, as->base, as->nmel * width);
while (as->nmel > 0 && bs_nmel > 0) {
if (cmp(a, b) <= 0) {
swap(target, a, width);
a += width; as->nmel--;
} else {
swap(target, b, width);
b += width; bs_nmel--;
}
target += width;
}
swap(target, a, as->nmel * width);
}
static char *find_min_block(char *base, size_t count, size_t bwidth, size_t width, cmpfun cmp)
{
char *min = base;
for (base += bwidth, count--; count--; base += bwidth) {
if (cmp(min + bwidth - width, base) > 0) min = base;
}
return min;
}
static size_t roll(struct array *a, struct array *b,
size_t bwidth, size_t width, char **mina, cmpfun cmp)
{
size_t iters = 0;
while (b->nmel && cmp(b->base , *mina + bwidth - width) < 0) {
swap(a->base, b->base, bwidth);
if (*mina == a->base) *mina = b->base;
a->base += bwidth;
b->base += bwidth;
b->nmel--;
iters++;
}
return iters;
}
void wikisort(void *unsorted, size_t nmel, size_t width, cmpfun cmp)
{
char *base = unsorted;
if (nmel <= MAX_SORTNET) {
sorting_network(base, nmel, width, cmp);
return;
}
size_t bnmel = sqrt(nmel); /* elements in a block */
size_t bcount = nmel / bnmel;
size_t bwidth = bnmel * width;
/* temporary buffer: nmel is measured in array elements */
struct array buf = { .base = base, .nmel = bnmel + nmel % bnmel };
/* A and B subarrays: nmel is measured in blocks of bnmel elements each */
struct array a = { .base = buf.base + width * buf.nmel, .nmel = (bcount - 1) / 2 };
struct array b = { .base = a.base + bwidth * a.nmel, .nmel = bcount - 1 - a.nmel };
/* sort the buffer as if it were part of the a array */
wikisort(buf.base, buf.nmel + a.nmel * bnmel, width, cmp);
wikisort(b.base, b.nmel * bnmel, width, cmp);
/* if already sorted, nothing to do */
if (cmp(b.base - width, b.base) <= 0) return;
/* if blocks in b are all less than those in a, just need a rotate */
if (cmp(base + (nmel - 1) * width, base) <= 0) {
rotate(base, nmel * width, (a.nmel * bnmel + buf.nmel) * width);
return;
}
struct array penda = { 0 };
size_t pendb_nmel = 0;
char *mina = a.base;
while (a.nmel) {
size_t rolled_blocks = b.nmel ? roll(&a, &b, bwidth, width, &mina, cmp) : 0;
/* move mina block to immediately after rolled b blocks */
if (mina != a.base) swap(mina, a.base, bwidth);
/* rotate mina into correct spot in the last rolled b */
pendb_nmel += rolled_blocks * bnmel;
if (pendb_nmel) {
size_t offset = pendb_nmel - binary_search(a.base, a.base - pendb_nmel * width, pendb_nmel, width, cmp);
rotate(a.base - offset * width, (bnmel + offset) * width, offset * width);
pendb_nmel -= offset;
if (penda.nmel && pendb_nmel) {
merge_blocks(buf.base, &penda, pendb_nmel, width, cmp);
}
penda.base = a.base - offset * width;
penda.nmel = bnmel;
pendb_nmel = offset;
} else {
penda.nmel = 0;
pendb_nmel = 0;
}
a.base += bwidth;
if (--a.nmel) {
mina = find_min_block(a.base, a.nmel, bwidth, width, cmp);
}
}
if (penda.nmel) {
merge_blocks(buf.base, &penda, b.nmel * bnmel + pendb_nmel, width, cmp);
}
wikisort(buf.base, buf.nmel, width, cmp);
distribute_buffer(buf.base, buf.nmel, nmel - buf.nmel, width, cmp);
}
|
