|
1
|
|
/* -*- c -*- */
|
|
2
|
|
|
|
3
|
|
/*
|
|
4
|
|
* The purpose of this module is to add faster sort functions
|
|
5
|
|
* that are type-specific. This is done by altering the
|
|
6
|
|
* function table for the builtin descriptors.
|
|
7
|
|
*
|
|
8
|
|
* These sorting functions are copied almost directly from numarray
|
|
9
|
|
* with a few modifications (complex comparisons compare the imaginary
|
|
10
|
|
* part if the real parts are equal, for example), and the names
|
|
11
|
|
* are changed.
|
|
12
|
|
*
|
|
13
|
|
* The original sorting code is due to Charles R. Harris who wrote
|
|
14
|
|
* it for numarray.
|
|
15
|
|
*/
|
|
16
|
|
|
|
17
|
|
/*
|
|
18
|
|
* Quick sort is usually the fastest, but the worst case scenario can
|
|
19
|
|
* be slower than the merge and heap sorts. The merge sort requires
|
|
20
|
|
* extra memory and so for large arrays may not be useful.
|
|
21
|
|
*
|
|
22
|
|
* The merge sort is *stable*, meaning that equal components
|
|
23
|
|
* are unmoved from their entry versions, so it can be used to
|
|
24
|
|
* implement lexigraphic sorting on multiple keys.
|
|
25
|
|
*
|
|
26
|
|
* The heap sort is included for completeness.
|
|
27
|
|
*/
|
|
28
|
|
|
|
29
|
|
#define NPY_NO_DEPRECATED_API NPY_API_VERSION
|
|
30
|
|
|
|
31
|
|
#include "npy_sort.h"
|
|
32
|
|
#include "npysort_common.h"
|
|
33
|
|
#include <stdlib.h>
|
|
34
|
|
|
|
35
|
|
#define NOT_USED NPY_UNUSED(unused)
|
|
36
|
|
#define PYA_QS_STACK 100
|
|
37
|
|
#define SMALL_QUICKSORT 15
|
|
38
|
|
#define SMALL_MERGESORT 20
|
|
39
|
|
#define SMALL_STRING 16
|
|
40
|
|
|
|
41
|
|
|
|
42
|
|
/*
|
|
43
|
|
*****************************************************************************
|
|
44
|
|
** NUMERIC SORTS **
|
|
45
|
|
*****************************************************************************
|
|
46
|
|
*/
|
|
47
|
|
|
|
48
|
|
|
|
49
|
|
/**begin repeat
|
|
50
|
|
*
|
|
51
|
|
* #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
|
|
52
|
|
* LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE,
|
|
53
|
|
* CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
|
|
54
|
|
* #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
|
|
55
|
|
* longlong, ulonglong, half, float, double, longdouble,
|
|
56
|
|
* cfloat, cdouble, clongdouble, datetime, timedelta#
|
|
57
|
|
* #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
|
|
58
|
|
* npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong,
|
|
59
|
|
* npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat,
|
|
60
|
|
* npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta#
|
|
61
|
|
*/
|
|
62
|
|
|
|
63
|
|
static void
|
|
64
|
0
|
mergesort0_@suff@(@type@ *pl, @type@ *pr, @type@ *pw)
|
|
65
|
|
{
|
|
66
|
|
@type@ vp, *pi, *pj, *pk, *pm;
|
|
67
|
|
|
|
68
|
0
|
if (pr - pl > SMALL_MERGESORT) {
|
|
69
|
|
/* merge sort */
|
|
70
|
0
|
pm = pl + ((pr - pl) >> 1);
|
|
71
|
0
|
mergesort0_@suff@(pl, pm, pw);
|
|
72
|
0
|
mergesort0_@suff@(pm, pr, pw);
|
|
73
|
0
|
for (pi = pw, pj = pl; pj < pm;) {
|
|
74
|
0
|
*pi++ = *pj++;
|
|
75
|
|
}
|
|
76
|
0
|
pi = pw + (pm - pl);
|
|
77
|
0
|
pj = pw;
|
|
78
|
0
|
pk = pl;
|
|
79
|
0
|
while (pj < pi && pm < pr) {
|
|
80
|
0
|
if (@TYPE@_LT(*pm, *pj)) {
|
|
81
|
0
|
*pk++ = *pm++;
|
|
82
|
|
}
|
|
83
|
|
else {
|
|
84
|
0
|
*pk++ = *pj++;
|
|
85
|
|
}
|
|
86
|
|
}
|
|
87
|
0
|
while(pj < pi) {
|
|
88
|
0
|
*pk++ = *pj++;
|
|
89
|
|
}
|
|
90
|
|
}
|
|
91
|
|
else {
|
|
92
|
|
/* insertion sort */
|
|
93
|
0
|
for (pi = pl + 1; pi < pr; ++pi) {
|
|
94
|
0
|
vp = *pi;
|
|
95
|
0
|
pj = pi;
|
|
96
|
0
|
pk = pi - 1;
|
|
97
|
0
|
while (pj > pl && @TYPE@_LT(vp, *pk)) {
|
|
98
|
0
|
*pj-- = *pk--;
|
|
99
|
|
}
|
|
100
|
0
|
*pj = vp;
|
|
101
|
|
}
|
|
102
|
|
}
|
|
103
|
0
|
}
|
|
104
|
|
|
|
105
|
|
|
|
106
|
|
NPY_NO_EXPORT int
|
|
107
|
0
|
mergesort_@suff@(void *start, npy_intp num, void *NOT_USED)
|
|
108
|
|
{
|
|
109
|
|
@type@ *pl, *pr, *pw;
|
|
110
|
|
|
|
111
|
0
|
pl = start;
|
|
112
|
0
|
pr = pl + num;
|
|
113
|
0
|
pw = malloc((num/2) * sizeof(@type@));
|
|
114
|
0
|
if (pw == NULL) {
|
|
115
|
|
return -NPY_ENOMEM;
|
|
116
|
|
}
|
|
117
|
0
|
mergesort0_@suff@(pl, pr, pw);
|
|
118
|
|
|
|
119
|
0
|
free(pw);
|
|
120
|
0
|
return 0;
|
|
121
|
|
}
|
|
122
|
|
|
|
123
|
|
|
|
124
|
|
static void
|
|
125
|
0
|
amergesort0_@suff@(npy_intp *pl, npy_intp *pr, @type@ *v, npy_intp *pw)
|
|
126
|
|
{
|
|
127
|
|
@type@ vp;
|
|
128
|
|
npy_intp vi, *pi, *pj, *pk, *pm;
|
|
129
|
|
|
|
130
|
0
|
if (pr - pl > SMALL_MERGESORT) {
|
|
131
|
|
/* merge sort */
|
|
132
|
0
|
pm = pl + ((pr - pl) >> 1);
|
|
133
|
0
|
amergesort0_@suff@(pl, pm, v, pw);
|
|
134
|
0
|
amergesort0_@suff@(pm, pr, v, pw);
|
|
135
|
0
|
for (pi = pw, pj = pl; pj < pm;) {
|
|
136
|
0
|
*pi++ = *pj++;
|
|
137
|
|
}
|
|
138
|
0
|
pi = pw + (pm - pl);
|
|
139
|
0
|
pj = pw;
|
|
140
|
0
|
pk = pl;
|
|
141
|
0
|
while (pj < pi && pm < pr) {
|
|
142
|
0
|
if (@TYPE@_LT(v[*pm], v[*pj])) {
|
|
143
|
0
|
*pk++ = *pm++;
|
|
144
|
|
}
|
|
145
|
|
else {
|
|
146
|
0
|
*pk++ = *pj++;
|
|
147
|
|
}
|
|
148
|
|
}
|
|
149
|
0
|
while(pj < pi) {
|
|
150
|
0
|
*pk++ = *pj++;
|
|
151
|
|
}
|
|
152
|
|
}
|
|
153
|
|
else {
|
|
154
|
|
/* insertion sort */
|
|
155
|
0
|
for (pi = pl + 1; pi < pr; ++pi) {
|
|
156
|
0
|
vi = *pi;
|
|
157
|
0
|
vp = v[vi];
|
|
158
|
0
|
pj = pi;
|
|
159
|
0
|
pk = pi - 1;
|
|
160
|
0
|
while (pj > pl && @TYPE@_LT(vp, v[*pk])) {
|
|
161
|
0
|
*pj-- = *pk--;
|
|
162
|
|
}
|
|
163
|
0
|
*pj = vi;
|
|
164
|
|
}
|
|
165
|
|
}
|
|
166
|
0
|
}
|
|
167
|
|
|
|
168
|
|
|
|
169
|
|
NPY_NO_EXPORT int
|
|
170
|
0
|
amergesort_@suff@(void *v, npy_intp *tosort, npy_intp num, void *NOT_USED)
|
|
171
|
|
{
|
|
172
|
|
npy_intp *pl, *pr, *pw;
|
|
173
|
|
|
|
174
|
0
|
pl = tosort;
|
|
175
|
0
|
pr = pl + num;
|
|
176
|
0
|
pw = malloc((num/2) * sizeof(npy_intp));
|
|
177
|
0
|
if (pw == NULL) {
|
|
178
|
|
return -NPY_ENOMEM;
|
|
179
|
|
}
|
|
180
|
0
|
amergesort0_@suff@(pl, pr, v, pw);
|
|
181
|
0
|
free(pw);
|
|
182
|
|
|
|
183
|
0
|
return 0;
|
|
184
|
|
}
|
|
185
|
|
|
|
186
|
|
/**end repeat**/
|
|
187
|
|
|
|
188
|
|
|
|
189
|
|
/*
|
|
190
|
|
*****************************************************************************
|
|
191
|
|
** STRING SORTS **
|
|
192
|
|
*****************************************************************************
|
|
193
|
|
*/
|
|
194
|
|
|
|
195
|
|
|
|
196
|
|
/**begin repeat
|
|
197
|
|
*
|
|
198
|
|
* #TYPE = STRING, UNICODE#
|
|
199
|
|
* #suff = string, unicode#
|
|
200
|
|
* #type = npy_char, npy_ucs4#
|
|
201
|
|
*/
|
|
202
|
|
|
|
203
|
|
static void
|
|
204
|
0
|
mergesort0_@suff@(@type@ *pl, @type@ *pr, @type@ *pw, @type@ *vp, size_t len)
|
|
205
|
|
{
|
|
206
|
|
@type@ *pi, *pj, *pk, *pm;
|
|
207
|
|
|
|
208
|
0
|
if ((size_t)(pr - pl) > SMALL_MERGESORT*len) {
|
|
209
|
|
/* merge sort */
|
|
210
|
0
|
pm = pl + (((pr - pl)/len) >> 1)*len;
|
|
211
|
0
|
mergesort0_@suff@(pl, pm, pw, vp, len);
|
|
212
|
0
|
mergesort0_@suff@(pm, pr, pw, vp, len);
|
|
213
|
0
|
@TYPE@_COPY(pw, pl, pm - pl);
|
|
214
|
0
|
pi = pw + (pm - pl);
|
|
215
|
0
|
pj = pw;
|
|
216
|
0
|
pk = pl;
|
|
217
|
0
|
while (pj < pi && pm < pr) {
|
|
218
|
0
|
if (@TYPE@_LT(pm, pj, len)) {
|
|
219
|
0
|
@TYPE@_COPY(pk, pm, len);
|
|
220
|
0
|
pm += len;
|
|
221
|
0
|
pk += len;
|
|
222
|
|
}
|
|
223
|
|
else {
|
|
224
|
0
|
@TYPE@_COPY(pk, pj, len);
|
|
225
|
0
|
pj += len;
|
|
226
|
0
|
pk += len;
|
|
227
|
|
}
|
|
228
|
|
}
|
|
229
|
0
|
@TYPE@_COPY(pk, pj, pi - pj);
|
|
230
|
|
}
|
|
231
|
|
else {
|
|
232
|
|
/* insertion sort */
|
|
233
|
0
|
for (pi = pl + len; pi < pr; pi += len) {
|
|
234
|
0
|
@TYPE@_COPY(vp, pi, len);
|
|
235
|
0
|
pj = pi;
|
|
236
|
0
|
pk = pi - len;
|
|
237
|
0
|
while (pj > pl && @TYPE@_LT(vp, pk, len)) {
|
|
238
|
0
|
@TYPE@_COPY(pj, pk, len);
|
|
239
|
0
|
pj -= len;
|
|
240
|
0
|
pk -= len;
|
|
241
|
|
}
|
|
242
|
0
|
@TYPE@_COPY(pj, vp, len);
|
|
243
|
|
}
|
|
244
|
|
}
|
|
245
|
0
|
}
|
|
246
|
|
|
|
247
|
|
|
|
248
|
|
NPY_NO_EXPORT int
|
|
249
|
0
|
mergesort_@suff@(void *start, npy_intp num, void *varr)
|
|
250
|
|
{
|
|
251
|
0
|
PyArrayObject *arr = varr;
|
|
252
|
0
|
size_t elsize = PyArray_ITEMSIZE(arr);
|
|
253
|
0
|
size_t len = elsize / sizeof(@type@);
|
|
254
|
|
@type@ *pl, *pr, *pw, *vp;
|
|
255
|
0
|
int err = 0;
|
|
256
|
|
|
|
257
|
|
/* Items that have zero size don't make sense to sort */
|
|
258
|
0
|
if (elsize == 0) {
|
|
259
|
|
return 0;
|
|
260
|
|
}
|
|
261
|
|
|
|
262
|
0
|
pl = start;
|
|
263
|
0
|
pr = pl + num*len;
|
|
264
|
0
|
pw = malloc((num/2) * elsize);
|
|
265
|
0
|
if (pw == NULL) {
|
|
266
|
|
err = -NPY_ENOMEM;
|
|
267
|
|
goto fail_0;
|
|
268
|
|
}
|
|
269
|
0
|
vp = malloc(elsize);
|
|
270
|
0
|
if (vp == NULL) {
|
|
271
|
|
err = -NPY_ENOMEM;
|
|
272
|
|
goto fail_1;
|
|
273
|
|
}
|
|
274
|
0
|
mergesort0_@suff@(pl, pr, pw, vp, len);
|
|
275
|
|
|
|
276
|
0
|
free(vp);
|
|
277
|
0
|
fail_1:
|
|
278
|
0
|
free(pw);
|
|
279
|
|
fail_0:
|
|
280
|
|
return err;
|
|
281
|
|
}
|
|
282
|
|
|
|
283
|
|
|
|
284
|
|
static void
|
|
285
|
0
|
amergesort0_@suff@(npy_intp *pl, npy_intp *pr, @type@ *v, npy_intp *pw, size_t len)
|
|
286
|
|
{
|
|
287
|
|
@type@ *vp;
|
|
288
|
|
npy_intp vi, *pi, *pj, *pk, *pm;
|
|
289
|
|
|
|
290
|
0
|
if (pr - pl > SMALL_MERGESORT) {
|
|
291
|
|
/* merge sort */
|
|
292
|
0
|
pm = pl + ((pr - pl) >> 1);
|
|
293
|
0
|
amergesort0_@suff@(pl, pm, v, pw, len);
|
|
294
|
0
|
amergesort0_@suff@(pm, pr, v, pw, len);
|
|
295
|
0
|
for (pi = pw, pj = pl; pj < pm;) {
|
|
296
|
0
|
*pi++ = *pj++;
|
|
297
|
|
}
|
|
298
|
0
|
pi = pw + (pm - pl);
|
|
299
|
0
|
pj = pw;
|
|
300
|
0
|
pk = pl;
|
|
301
|
0
|
while (pj < pi && pm < pr) {
|
|
302
|
0
|
if (@TYPE@_LT(v + (*pm)*len, v + (*pj)*len, len)) {
|
|
303
|
0
|
*pk++ = *pm++;
|
|
304
|
|
}
|
|
305
|
|
else {
|
|
306
|
0
|
*pk++ = *pj++;
|
|
307
|
|
}
|
|
308
|
|
}
|
|
309
|
0
|
while (pj < pi) {
|
|
310
|
0
|
*pk++ = *pj++;
|
|
311
|
|
}
|
|
312
|
|
}
|
|
313
|
|
else {
|
|
314
|
|
/* insertion sort */
|
|
315
|
0
|
for (pi = pl + 1; pi < pr; ++pi) {
|
|
316
|
0
|
vi = *pi;
|
|
317
|
0
|
vp = v + vi*len;
|
|
318
|
0
|
pj = pi;
|
|
319
|
0
|
pk = pi - 1;
|
|
320
|
0
|
while (pj > pl && @TYPE@_LT(vp, v + (*pk)*len, len)) {
|
|
321
|
0
|
*pj-- = *pk--;
|
|
322
|
|
}
|
|
323
|
0
|
*pj = vi;
|
|
324
|
|
}
|
|
325
|
|
}
|
|
326
|
0
|
}
|
|
327
|
|
|
|
328
|
|
|
|
329
|
|
NPY_NO_EXPORT int
|
|
330
|
0
|
amergesort_@suff@(void *v, npy_intp *tosort, npy_intp num, void *varr)
|
|
331
|
|
{
|
|
332
|
0
|
PyArrayObject *arr = varr;
|
|
333
|
0
|
size_t elsize = PyArray_ITEMSIZE(arr);
|
|
334
|
0
|
size_t len = elsize / sizeof(@type@);
|
|
335
|
|
npy_intp *pl, *pr, *pw;
|
|
336
|
|
|
|
337
|
|
/* Items that have zero size don't make sense to sort */
|
|
338
|
0
|
if (elsize == 0) {
|
|
339
|
|
return 0;
|
|
340
|
|
}
|
|
341
|
|
|
|
342
|
0
|
pl = tosort;
|
|
343
|
0
|
pr = pl + num;
|
|
344
|
0
|
pw = malloc((num/2) * sizeof(npy_intp));
|
|
345
|
0
|
if (pw == NULL) {
|
|
346
|
|
return -NPY_ENOMEM;
|
|
347
|
|
}
|
|
348
|
0
|
amergesort0_@suff@(pl, pr, v, pw, len);
|
|
349
|
0
|
free(pw);
|
|
350
|
|
|
|
351
|
0
|
return 0;
|
|
352
|
|
}
|
|
353
|
|
|
|
354
|
|
/**end repeat**/
|
|
355
|
|
|
|
356
|
|
|
|
357
|
|
/*
|
|
358
|
|
*****************************************************************************
|
|
359
|
|
** GENERIC SORT **
|
|
360
|
|
*****************************************************************************
|
|
361
|
|
*/
|
|
362
|
|
|
|
363
|
|
|
|
364
|
|
static void
|
|
365
|
0
|
npy_mergesort0(char *pl, char *pr, char *pw, char *vp, npy_intp elsize,
|
|
366
|
|
PyArray_CompareFunc *cmp, PyArrayObject *arr)
|
|
367
|
|
{
|
|
368
|
|
char *pi, *pj, *pk, *pm;
|
|
369
|
|
|
|
370
|
0
|
if (pr - pl > SMALL_MERGESORT*elsize) {
|
|
371
|
|
/* merge sort */
|
|
372
|
0
|
pm = pl + (((pr - pl)/elsize) >> 1)*elsize;
|
|
373
|
0
|
npy_mergesort0(pl, pm, pw, vp, elsize, cmp, arr);
|
|
374
|
0
|
npy_mergesort0(pm, pr, pw, vp, elsize, cmp, arr);
|
|
375
|
0
|
GENERIC_COPY(pw, pl, pm - pl);
|
|
376
|
0
|
pi = pw + (pm - pl);
|
|
377
|
0
|
pj = pw;
|
|
378
|
0
|
pk = pl;
|
|
379
|
0
|
while (pj < pi && pm < pr) {
|
|
380
|
0
|
if (cmp(pm, pj, arr) < 0) {
|
|
381
|
0
|
GENERIC_COPY(pk, pm, elsize);
|
|
382
|
0
|
pm += elsize;
|
|
383
|
0
|
pk += elsize;
|
|
384
|
|
}
|
|
385
|
|
else {
|
|
386
|
0
|
GENERIC_COPY(pk, pj, elsize);
|
|
387
|
0
|
pj += elsize;
|
|
388
|
0
|
pk += elsize;
|
|
389
|
|
}
|
|
390
|
|
}
|
|
391
|
0
|
GENERIC_COPY(pk, pj, pi - pj);
|
|
392
|
|
}
|
|
393
|
|
else {
|
|
394
|
|
/* insertion sort */
|
|
395
|
0
|
for (pi = pl + elsize; pi < pr; pi += elsize) {
|
|
396
|
0
|
GENERIC_COPY(vp, pi, elsize);
|
|
397
|
0
|
pj = pi;
|
|
398
|
0
|
pk = pi - elsize;
|
|
399
|
0
|
while (pj > pl && cmp(vp, pk, arr) < 0) {
|
|
400
|
0
|
GENERIC_COPY(pj, pk, elsize);
|
|
401
|
0
|
pj -= elsize;
|
|
402
|
0
|
pk -= elsize;
|
|
403
|
|
}
|
|
404
|
0
|
GENERIC_COPY(pj, vp, elsize);
|
|
405
|
|
}
|
|
406
|
|
}
|
|
407
|
0
|
}
|
|
408
|
|
|
|
409
|
|
|
|
410
|
|
NPY_NO_EXPORT int
|
|
411
|
0
|
npy_mergesort(void *start, npy_intp num, void *varr)
|
|
412
|
|
{
|
|
413
|
0
|
PyArrayObject *arr = varr;
|
|
414
|
0
|
npy_intp elsize = PyArray_ITEMSIZE(arr);
|
|
415
|
0
|
PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
|
|
416
|
0
|
char *pl = start;
|
|
417
|
0
|
char *pr = pl + num*elsize;
|
|
418
|
|
char *pw;
|
|
419
|
|
char *vp;
|
|
420
|
0
|
int err = -NPY_ENOMEM;
|
|
421
|
|
|
|
422
|
|
/* Items that have zero size don't make sense to sort */
|
|
423
|
0
|
if (elsize == 0) {
|
|
424
|
|
return 0;
|
|
425
|
|
}
|
|
426
|
|
|
|
427
|
0
|
pw = malloc((num >> 1) *elsize);
|
|
428
|
0
|
vp = malloc(elsize);
|
|
429
|
|
|
|
430
|
0
|
if (pw != NULL && vp != NULL) {
|
|
431
|
0
|
npy_mergesort0(pl, pr, pw, vp, elsize, cmp, arr);
|
|
432
|
0
|
err = 0;
|
|
433
|
|
}
|
|
434
|
|
|
|
435
|
0
|
free(vp);
|
|
436
|
0
|
free(pw);
|
|
437
|
|
|
|
438
|
0
|
return err;
|
|
439
|
|
}
|
|
440
|
|
|
|
441
|
|
|
|
442
|
|
static void
|
|
443
|
0
|
npy_amergesort0(npy_intp *pl, npy_intp *pr, char *v, npy_intp *pw,
|
|
444
|
|
npy_intp elsize, PyArray_CompareFunc *cmp, PyArrayObject *arr)
|
|
445
|
|
{
|
|
446
|
|
char *vp;
|
|
447
|
|
npy_intp vi, *pi, *pj, *pk, *pm;
|
|
448
|
|
|
|
449
|
0
|
if (pr - pl > SMALL_MERGESORT) {
|
|
450
|
|
/* merge sort */
|
|
451
|
0
|
pm = pl + ((pr - pl) >> 1);
|
|
452
|
0
|
npy_amergesort0(pl, pm, v, pw, elsize, cmp, arr);
|
|
453
|
0
|
npy_amergesort0(pm, pr, v, pw, elsize, cmp, arr);
|
|
454
|
0
|
for (pi = pw, pj = pl; pj < pm;) {
|
|
455
|
0
|
*pi++ = *pj++;
|
|
456
|
|
}
|
|
457
|
0
|
pi = pw + (pm - pl);
|
|
458
|
0
|
pj = pw;
|
|
459
|
0
|
pk = pl;
|
|
460
|
0
|
while (pj < pi && pm < pr) {
|
|
461
|
0
|
if (cmp(v + (*pm)*elsize, v + (*pj)*elsize, arr) < 0) {
|
|
462
|
0
|
*pk++ = *pm++;
|
|
463
|
|
}
|
|
464
|
|
else {
|
|
465
|
0
|
*pk++ = *pj++;
|
|
466
|
|
}
|
|
467
|
|
}
|
|
468
|
0
|
while (pj < pi) {
|
|
469
|
0
|
*pk++ = *pj++;
|
|
470
|
|
}
|
|
471
|
|
}
|
|
472
|
|
else {
|
|
473
|
|
/* insertion sort */
|
|
474
|
0
|
for (pi = pl + 1; pi < pr; ++pi) {
|
|
475
|
0
|
vi = *pi;
|
|
476
|
0
|
vp = v + vi*elsize;
|
|
477
|
0
|
pj = pi;
|
|
478
|
0
|
pk = pi - 1;
|
|
479
|
0
|
while (pj > pl && cmp(vp, v + (*pk)*elsize, arr) < 0) {
|
|
480
|
0
|
*pj-- = *pk--;
|
|
481
|
|
}
|
|
482
|
0
|
*pj = vi;
|
|
483
|
|
}
|
|
484
|
|
}
|
|
485
|
0
|
}
|
|
486
|
|
|
|
487
|
|
|
|
488
|
|
NPY_NO_EXPORT int
|
|
489
|
0
|
npy_amergesort(void *v, npy_intp *tosort, npy_intp num, void *varr)
|
|
490
|
|
{
|
|
491
|
0
|
PyArrayObject *arr = varr;
|
|
492
|
0
|
npy_intp elsize = PyArray_ITEMSIZE(arr);
|
|
493
|
0
|
PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
|
|
494
|
|
npy_intp *pl, *pr, *pw;
|
|
495
|
|
|
|
496
|
|
/* Items that have zero size don't make sense to sort */
|
|
497
|
0
|
if (elsize == 0) {
|
|
498
|
|
return 0;
|
|
499
|
|
}
|
|
500
|
|
|
|
501
|
0
|
pl = tosort;
|
|
502
|
0
|
pr = pl + num;
|
|
503
|
0
|
pw = malloc((num >> 1) * sizeof(npy_intp));
|
|
504
|
0
|
if (pw == NULL) {
|
|
505
|
|
return -NPY_ENOMEM;
|
|
506
|
|
}
|
|
507
|
0
|
npy_amergesort0(pl, pr, v, pw, elsize, cmp, arr);
|
|
508
|
0
|
free(pw);
|
|
509
|
|
|
|
510
|
0
|
return 0;
|
|
511
|
|
}
|
BvB93