| 412 | } |
| 413 | |
| 414 | static void |
| 415 | npy_amergesort0(npy_intp *pl, npy_intp *pr, char *v, npy_intp *pw, |
| 416 | npy_intp elsize, PyArray_CompareFunc *cmp, PyArrayObject *arr) |
| 417 | { |
| 418 | char *vp; |
| 419 | npy_intp vi, *pi, *pj, *pk, *pm; |
| 420 | |
| 421 | if (pr - pl > SMALL_MERGESORT) { |
| 422 | /* merge sort */ |
| 423 | pm = pl + ((pr - pl) >> 1); |
| 424 | npy_amergesort0(pl, pm, v, pw, elsize, cmp, arr); |
| 425 | npy_amergesort0(pm, pr, v, pw, elsize, cmp, arr); |
| 426 | for (pi = pw, pj = pl; pj < pm;) { |
| 427 | *pi++ = *pj++; |
| 428 | } |
| 429 | pi = pw + (pm - pl); |
| 430 | pj = pw; |
| 431 | pk = pl; |
| 432 | while (pj < pi && pm < pr) { |
| 433 | if (cmp(v + (*pm) * elsize, v + (*pj) * elsize, arr) < 0) { |
| 434 | *pk++ = *pm++; |
| 435 | } |
| 436 | else { |
| 437 | *pk++ = *pj++; |
| 438 | } |
| 439 | } |
| 440 | while (pj < pi) { |
| 441 | *pk++ = *pj++; |
| 442 | } |
| 443 | } |
| 444 | else { |
| 445 | /* insertion sort */ |
| 446 | for (pi = pl + 1; pi < pr; ++pi) { |
| 447 | vi = *pi; |
| 448 | vp = v + vi * elsize; |
| 449 | pj = pi; |
| 450 | pk = pi - 1; |
| 451 | while (pj > pl && cmp(vp, v + (*pk) * elsize, arr) < 0) { |
| 452 | *pj-- = *pk--; |
| 453 | } |
| 454 | *pj = vi; |
| 455 | } |
| 456 | } |
| 457 | } |
| 458 | |
| 459 | NPY_NO_EXPORT int |
| 460 | npy_amergesort(void *v, npy_intp *tosort, npy_intp num, void *varr) |