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 is O(N^2) so ``` 19 ``` * the code switches to the O(NlogN) worst case heapsort if not enough progress ``` 20 ``` * is made on the large side of the two quicksort partitions. This improves the ``` 21 ``` * worst case while still retaining the speed of quicksort for the common case. ``` 22 ``` * This is variant known as introsort. ``` 23 ``` * ``` 24 ``` * ``` 25 ``` * def introsort(lower, higher, recursion_limit=log2(higher - lower + 1) * 2): ``` 26 ``` * # sort remainder with heapsort if we are not making enough progress ``` 27 ``` * # we arbitrarily choose 2 * log(n) as the cutoff point ``` 28 ``` * if recursion_limit < 0: ``` 29 ``` * heapsort(lower, higher) ``` 30 ``` * return ``` 31 ``` * ``` 32 ``` * if lower < higher: ``` 33 ``` * pivot_pos = partition(lower, higher) ``` 34 ``` * # recurse into smaller first and leave larger on stack ``` 35 ``` * # this limits the required stack space ``` 36 ``` * if (pivot_pos - lower > higher - pivot_pos): ``` 37 ``` * quicksort(pivot_pos + 1, higher, recursion_limit - 1) ``` 38 ``` * quicksort(lower, pivot_pos, recursion_limit - 1) ``` 39 ``` * else: ``` 40 ``` * quicksort(lower, pivot_pos, recursion_limit - 1) ``` 41 ``` * quicksort(pivot_pos + 1, higher, recursion_limit - 1) ``` 42 ``` * ``` 43 ``` * ``` 44 ``` * the below code implements this converted to an iteration and as an ``` 45 ``` * additional minor optimization skips the recursion depth checking on the ``` 46 ``` * smaller partition as it is always less than half of the remaining data and ``` 47 ``` * will thus terminate fast enough ``` 48 ``` */ ``` 49 50 ```#define NPY_NO_DEPRECATED_API NPY_API_VERSION ``` 51 52 ```#include "npy_sort.h" ``` 53 ```#include "npysort_common.h" ``` 54 ```#include ``` 55 56 ```#define NOT_USED NPY_UNUSED(unused) ``` 57 ```/* ``` 58 ``` * pushing largest partition has upper bound of log2(n) space ``` 59 ``` * we store two pointers each time ``` 60 ``` */ ``` 61 ```#define PYA_QS_STACK (NPY_BITSOF_INTP * 2) ``` 62 ```#define SMALL_QUICKSORT 15 ``` 63 ```#define SMALL_MERGESORT 20 ``` 64 ```#define SMALL_STRING 16 ``` 65 66 67 ```/* ``` 68 ``` ***************************************************************************** ``` 69 ``` ** NUMERIC SORTS ** ``` 70 ``` ***************************************************************************** ``` 71 ``` */ ``` 72 73 74 ```/**begin repeat ``` 75 ``` * ``` 76 ``` * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG, ``` 77 ``` * LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, ``` 78 ``` * CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA# ``` 79 ``` * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong, ``` 80 ``` * longlong, ulonglong, half, float, double, longdouble, ``` 81 ``` * cfloat, cdouble, clongdouble, datetime, timedelta# ``` 82 ``` * #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int, ``` 83 ``` * npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong, ``` 84 ``` * npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat, ``` 85 ``` * npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta# ``` 86 ``` */ ``` 87 88 ```NPY_NO_EXPORT int ``` 89 1 ```quicksort_@suff@(void *start, npy_intp num, void *NOT_USED) ``` 90 ```{ ``` 91 ``` @type@ vp; ``` 92 1 ``` @type@ *pl = start; ``` 93 1 ``` @type@ *pr = pl + num - 1; ``` 94 ``` @type@ *stack[PYA_QS_STACK]; ``` 95 1 ``` @type@ **sptr = stack; ``` 96 ``` @type@ *pm, *pi, *pj, *pk; ``` 97 ``` int depth[PYA_QS_STACK]; ``` 98 1 ``` int * psdepth = depth; ``` 99 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 100 101 ``` for (;;) { ``` 102 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 103 1 ``` heapsort_@suff@(pl, pr - pl + 1, NULL); ``` 104 1 ``` goto stack_pop; ``` 105 ``` } ``` 106 1 ``` while ((pr - pl) > SMALL_QUICKSORT) { ``` 107 ``` /* quicksort partition */ ``` 108 1 ``` pm = pl + ((pr - pl) >> 1); ``` 109 1 ``` if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl); ``` 110 1 ``` if (@TYPE@_LT(*pr, *pm)) @TYPE@_SWAP(*pr, *pm); ``` 111 1 ``` if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl); ``` 112 1 ``` vp = *pm; ``` 113 1 ``` pi = pl; ``` 114 1 ``` pj = pr - 1; ``` 115 1 ``` @TYPE@_SWAP(*pm, *pj); ``` 116 1 ``` for (;;) { ``` 117 1 ``` do ++pi; while (@TYPE@_LT(*pi, vp)); ``` 118 1 ``` do --pj; while (@TYPE@_LT(vp, *pj)); ``` 119 1 ``` if (pi >= pj) { ``` 120 ``` break; ``` 121 ``` } ``` 122 1 ``` @TYPE@_SWAP(*pi,*pj); ``` 123 ``` } ``` 124 1 ``` pk = pr - 1; ``` 125 1 ``` @TYPE@_SWAP(*pi, *pk); ``` 126 ``` /* push largest partition on stack */ ``` 127 1 ``` if (pi - pl < pr - pi) { ``` 128 1 ``` *sptr++ = pi + 1; ``` 129 1 ``` *sptr++ = pr; ``` 130 1 ``` pr = pi - 1; ``` 131 ``` } ``` 132 ``` else { ``` 133 1 ``` *sptr++ = pl; ``` 134 1 ``` *sptr++ = pi - 1; ``` 135 1 ``` pl = pi + 1; ``` 136 ``` } ``` 137 1 ``` *psdepth++ = --cdepth; ``` 138 ``` } ``` 139 140 ``` /* insertion sort */ ``` 141 1 ``` for (pi = pl + 1; pi <= pr; ++pi) { ``` 142 1 ``` vp = *pi; ``` 143 1 ``` pj = pi; ``` 144 1 ``` pk = pi - 1; ``` 145 1 ``` while (pj > pl && @TYPE@_LT(vp, *pk)) { ``` 146 1 ``` *pj-- = *pk--; ``` 147 ``` } ``` 148 1 ``` *pj = vp; ``` 149 ``` } ``` 150 1 ```stack_pop: ``` 151 1 ``` if (sptr == stack) { ``` 152 ``` break; ``` 153 ``` } ``` 154 1 ``` pr = *(--sptr); ``` 155 1 ``` pl = *(--sptr); ``` 156 1 ``` cdepth = *(--psdepth); ``` 157 ``` } ``` 158 159 1 ``` return 0; ``` 160 ```} ``` 161 162 163 ```NPY_NO_EXPORT int ``` 164 1 ```aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *NOT_USED) ``` 165 ```{ ``` 166 1 ``` @type@ *v = vv; ``` 167 ``` @type@ vp; ``` 168 1 ``` npy_intp *pl = tosort; ``` 169 1 ``` npy_intp *pr = tosort + num - 1; ``` 170 ``` npy_intp *stack[PYA_QS_STACK]; ``` 171 1 ``` npy_intp **sptr = stack; ``` 172 ``` npy_intp *pm, *pi, *pj, *pk, vi; ``` 173 ``` int depth[PYA_QS_STACK]; ``` 174 1 ``` int * psdepth = depth; ``` 175 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 176 177 ``` for (;;) { ``` 178 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 179 1 ``` aheapsort_@suff@(vv, pl, pr - pl + 1, NULL); ``` 180 1 ``` goto stack_pop; ``` 181 ``` } ``` 182 1 ``` while ((pr - pl) > SMALL_QUICKSORT) { ``` 183 ``` /* quicksort partition */ ``` 184 1 ``` pm = pl + ((pr - pl) >> 1); ``` 185 1 ``` if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl); ``` 186 1 ``` if (@TYPE@_LT(v[*pr],v[*pm])) INTP_SWAP(*pr, *pm); ``` 187 1 ``` if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl); ``` 188 1 ``` vp = v[*pm]; ``` 189 1 ``` pi = pl; ``` 190 1 ``` pj = pr - 1; ``` 191 1 ``` INTP_SWAP(*pm, *pj); ``` 192 1 ``` for (;;) { ``` 193 1 ``` do ++pi; while (@TYPE@_LT(v[*pi], vp)); ``` 194 1 ``` do --pj; while (@TYPE@_LT(vp, v[*pj])); ``` 195 1 ``` if (pi >= pj) { ``` 196 ``` break; ``` 197 ``` } ``` 198 1 ``` INTP_SWAP(*pi, *pj); ``` 199 ``` } ``` 200 1 ``` pk = pr - 1; ``` 201 1 ``` INTP_SWAP(*pi,*pk); ``` 202 ``` /* push largest partition on stack */ ``` 203 1 ``` if (pi - pl < pr - pi) { ``` 204 1 ``` *sptr++ = pi + 1; ``` 205 1 ``` *sptr++ = pr; ``` 206 1 ``` pr = pi - 1; ``` 207 ``` } ``` 208 ``` else { ``` 209 1 ``` *sptr++ = pl; ``` 210 1 ``` *sptr++ = pi - 1; ``` 211 1 ``` pl = pi + 1; ``` 212 ``` } ``` 213 1 ``` *psdepth++ = --cdepth; ``` 214 ``` } ``` 215 216 ``` /* insertion sort */ ``` 217 1 ``` for (pi = pl + 1; pi <= pr; ++pi) { ``` 218 1 ``` vi = *pi; ``` 219 1 ``` vp = v[vi]; ``` 220 1 ``` pj = pi; ``` 221 1 ``` pk = pi - 1; ``` 222 1 ``` while (pj > pl && @TYPE@_LT(vp, v[*pk])) { ``` 223 1 ``` *pj-- = *pk--; ``` 224 ``` } ``` 225 1 ``` *pj = vi; ``` 226 ``` } ``` 227 1 ```stack_pop: ``` 228 1 ``` if (sptr == stack) { ``` 229 ``` break; ``` 230 ``` } ``` 231 1 ``` pr = *(--sptr); ``` 232 1 ``` pl = *(--sptr); ``` 233 1 ``` cdepth = *(--psdepth); ``` 234 ``` } ``` 235 236 1 ``` return 0; ``` 237 ```} ``` 238 239 ```/**end repeat**/ ``` 240 241 242 ```/* ``` 243 ``` ***************************************************************************** ``` 244 ``` ** STRING SORTS ** ``` 245 ``` ***************************************************************************** ``` 246 ``` */ ``` 247 248 249 ```/**begin repeat ``` 250 ``` * ``` 251 ``` * #TYPE = STRING, UNICODE# ``` 252 ``` * #suff = string, unicode# ``` 253 ``` * #type = npy_char, npy_ucs4# ``` 254 ``` */ ``` 255 256 ```NPY_NO_EXPORT int ``` 257 1 ```quicksort_@suff@(void *start, npy_intp num, void *varr) ``` 258 ```{ ``` 259 1 ``` PyArrayObject *arr = varr; ``` 260 1 ``` const size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@); ``` 261 ``` @type@ *vp; ``` 262 1 ``` @type@ *pl = start; ``` 263 1 ``` @type@ *pr = pl + (num - 1)*len; ``` 264 1 ``` @type@ *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk; ``` 265 ``` int depth[PYA_QS_STACK]; ``` 266 1 ``` int * psdepth = depth; ``` 267 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 268 269 ``` /* Items that have zero size don't make sense to sort */ ``` 270 1 ``` if (len == 0) { ``` 271 ``` return 0; ``` 272 ``` } ``` 273 274 1 ``` vp = malloc(PyArray_ITEMSIZE(arr)); ``` 275 1 ``` if (vp == NULL) { ``` 276 ``` return -NPY_ENOMEM; ``` 277 ``` } ``` 278 279 ``` for (;;) { ``` 280 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 281 0 ``` heapsort_@suff@(pl, (pr - pl) / len + 1, varr); ``` 282 0 ``` goto stack_pop; ``` 283 ``` } ``` 284 1 ``` while ((size_t)(pr - pl) > SMALL_QUICKSORT*len) { ``` 285 ``` /* quicksort partition */ ``` 286 1 ``` pm = pl + (((pr - pl)/len) >> 1)*len; ``` 287 1 ``` if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len); ``` 288 1 ``` if (@TYPE@_LT(pr, pm, len)) @TYPE@_SWAP(pr, pm, len); ``` 289 1 ``` if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len); ``` 290 1 ``` @TYPE@_COPY(vp, pm, len); ``` 291 1 ``` pi = pl; ``` 292 1 ``` pj = pr - len; ``` 293 ``` @TYPE@_SWAP(pm, pj, len); ``` 294 ``` for (;;) { ``` 295 1 ``` do pi += len; while (@TYPE@_LT(pi, vp, len)); ``` 296 1 ``` do pj -= len; while (@TYPE@_LT(vp, pj, len)); ``` 297 1 ``` if (pi >= pj) { ``` 298 ``` break; ``` 299 ``` } ``` 300 ``` @TYPE@_SWAP(pi, pj, len); ``` 301 ``` } ``` 302 ``` pk = pr - len; ``` 303 1 ``` @TYPE@_SWAP(pi, pk, len); ``` 304 ``` /* push largest partition on stack */ ``` 305 1 ``` if (pi - pl < pr - pi) { ``` 306 1 ``` *sptr++ = pi + len; ``` 307 1 ``` *sptr++ = pr; ``` 308 1 ``` pr = pi - len; ``` 309 ``` } ``` 310 ``` else { ``` 311 1 ``` *sptr++ = pl; ``` 312 1 ``` *sptr++ = pi - len; ``` 313 1 ``` pl = pi + len; ``` 314 ``` } ``` 315 1 ``` *psdepth++ = --cdepth; ``` 316 ``` } ``` 317 318 ``` /* insertion sort */ ``` 319 1 ``` for (pi = pl + len; pi <= pr; pi += len) { ``` 320 1 ``` @TYPE@_COPY(vp, pi, len); ``` 321 1 ``` pj = pi; ``` 322 1 ``` pk = pi - len; ``` 323 1 ``` while (pj > pl && @TYPE@_LT(vp, pk, len)) { ``` 324 1 ``` @TYPE@_COPY(pj, pk, len); ``` 325 1 ``` pj -= len; ``` 326 1 ``` pk -= len; ``` 327 ``` } ``` 328 1 ``` @TYPE@_COPY(pj, vp, len); ``` 329 ``` } ``` 330 1 ```stack_pop: ``` 331 1 ``` if (sptr == stack) { ``` 332 ``` break; ``` 333 ``` } ``` 334 1 ``` pr = *(--sptr); ``` 335 1 ``` pl = *(--sptr); ``` 336 1 ``` cdepth = *(--psdepth); ``` 337 ``` } ``` 338 339 1 ``` free(vp); ``` 340 1 ``` return 0; ``` 341 ```} ``` 342 343 344 ```NPY_NO_EXPORT int ``` 345 1 ```aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *varr) ``` 346 ```{ ``` 347 1 ``` @type@ *v = vv; ``` 348 1 ``` PyArrayObject *arr = varr; ``` 349 1 ``` size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@); ``` 350 ``` @type@ *vp; ``` 351 1 ``` npy_intp *pl = tosort; ``` 352 1 ``` npy_intp *pr = tosort + num - 1; ``` 353 ``` npy_intp *stack[PYA_QS_STACK]; ``` 354 1 ``` npy_intp **sptr=stack; ``` 355 ``` npy_intp *pm, *pi, *pj, *pk, vi; ``` 356 ``` int depth[PYA_QS_STACK]; ``` 357 1 ``` int * psdepth = depth; ``` 358 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 359 360 ``` /* Items that have zero size don't make sense to sort */ ``` 361 1 ``` if (len == 0) { ``` 362 ``` return 0; ``` 363 ``` } ``` 364 365 ``` for (;;) { ``` 366 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 367 0 ``` aheapsort_@suff@(vv, pl, pr - pl + 1, varr); ``` 368 0 ``` goto stack_pop; ``` 369 ``` } ``` 370 1 ``` while ((pr - pl) > SMALL_QUICKSORT) { ``` 371 ``` /* quicksort partition */ ``` 372 1 ``` pm = pl + ((pr - pl) >> 1); ``` 373 1 ``` if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl); ``` 374 1 ``` if (@TYPE@_LT(v + (*pr)*len, v + (*pm)*len, len)) INTP_SWAP(*pr, *pm); ``` 375 1 ``` if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl); ``` 376 1 ``` vp = v + (*pm)*len; ``` 377 1 ``` pi = pl; ``` 378 1 ``` pj = pr - 1; ``` 379 1 ``` INTP_SWAP(*pm,*pj); ``` 380 1 ``` for (;;) { ``` 381 1 ``` do ++pi; while (@TYPE@_LT(v + (*pi)*len, vp, len)); ``` 382 1 ``` do --pj; while (@TYPE@_LT(vp, v + (*pj)*len, len)); ``` 383 1 ``` if (pi >= pj) { ``` 384 ``` break; ``` 385 ``` } ``` 386 1 ``` INTP_SWAP(*pi,*pj); ``` 387 ``` } ``` 388 1 ``` pk = pr - 1; ``` 389 1 ``` INTP_SWAP(*pi,*pk); ``` 390 ``` /* push largest partition on stack */ ``` 391 1 ``` if (pi - pl < pr - pi) { ``` 392 1 ``` *sptr++ = pi + 1; ``` 393 1 ``` *sptr++ = pr; ``` 394 1 ``` pr = pi - 1; ``` 395 ``` } ``` 396 ``` else { ``` 397 1 ``` *sptr++ = pl; ``` 398 1 ``` *sptr++ = pi - 1; ``` 399 1 ``` pl = pi + 1; ``` 400 ``` } ``` 401 1 ``` *psdepth++ = --cdepth; ``` 402 ``` } ``` 403 404 ``` /* insertion sort */ ``` 405 1 ``` for (pi = pl + 1; pi <= pr; ++pi) { ``` 406 1 ``` vi = *pi; ``` 407 1 ``` vp = v + vi*len; ``` 408 1 ``` pj = pi; ``` 409 1 ``` pk = pi - 1; ``` 410 1 ``` while (pj > pl && @TYPE@_LT(vp, v + (*pk)*len, len)) { ``` 411 1 ``` *pj-- = *pk--; ``` 412 ``` } ``` 413 1 ``` *pj = vi; ``` 414 ``` } ``` 415 1 ```stack_pop: ``` 416 1 ``` if (sptr == stack) { ``` 417 ``` break; ``` 418 ``` } ``` 419 1 ``` pr = *(--sptr); ``` 420 1 ``` pl = *(--sptr); ``` 421 1 ``` cdepth = *(--psdepth); ``` 422 ``` } ``` 423 424 ``` return 0; ``` 425 ```} ``` 426 427 ```/**end repeat**/ ``` 428 429 430 ```/* ``` 431 ``` ***************************************************************************** ``` 432 ``` ** GENERIC SORT ** ``` 433 ``` ***************************************************************************** ``` 434 ``` */ ``` 435 436 437 ```NPY_NO_EXPORT int ``` 438 1 ```npy_quicksort(void *start, npy_intp num, void *varr) ``` 439 ```{ ``` 440 1 ``` PyArrayObject *arr = varr; ``` 441 1 ``` npy_intp elsize = PyArray_ITEMSIZE(arr); ``` 442 1 ``` PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare; ``` 443 ``` char *vp; ``` 444 1 ``` char *pl = start; ``` 445 1 ``` char *pr = pl + (num - 1)*elsize; ``` 446 ``` char *stack[PYA_QS_STACK]; ``` 447 1 ``` char **sptr = stack; ``` 448 ``` char *pm, *pi, *pj, *pk; ``` 449 ``` int depth[PYA_QS_STACK]; ``` 450 1 ``` int * psdepth = depth; ``` 451 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 452 453 ``` /* Items that have zero size don't make sense to sort */ ``` 454 1 ``` if (elsize == 0) { ``` 455 ``` return 0; ``` 456 ``` } ``` 457 458 1 ``` vp = malloc(elsize); ``` 459 1 ``` if (vp == NULL) { ``` 460 ``` return -NPY_ENOMEM; ``` 461 ``` } ``` 462 463 ``` for (;;) { ``` 464 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 465 1 ``` npy_heapsort(pl, (pr - pl) / elsize + 1, varr); ``` 466 1 ``` goto stack_pop; ``` 467 ``` } ``` 468 1 ``` while(pr - pl > SMALL_QUICKSORT*elsize) { ``` 469 ``` /* quicksort partition */ ``` 470 1 ``` pm = pl + (((pr - pl) / elsize) >> 1) * elsize; ``` 471 1 ``` if (cmp(pm, pl, arr) < 0) { ``` 472 ``` GENERIC_SWAP(pm, pl, elsize); ``` 473 ``` } ``` 474 1 ``` if (cmp(pr, pm, arr) < 0) { ``` 475 ``` GENERIC_SWAP(pr, pm, elsize); ``` 476 ``` } ``` 477 1 ``` if (cmp(pm, pl, arr) < 0) { ``` 478 ``` GENERIC_SWAP(pm, pl, elsize); ``` 479 ``` } ``` 480 1 ``` GENERIC_COPY(vp, pm, elsize); ``` 481 1 ``` pi = pl; ``` 482 1 ``` pj = pr - elsize; ``` 483 1 ``` GENERIC_SWAP(pm, pj, elsize); ``` 484 ``` /* ``` 485 ``` * Generic comparisons may be buggy, so don't rely on the sentinels ``` 486 ``` * to keep the pointers from going out of bounds. ``` 487 ``` */ ``` 488 ``` for (;;) { ``` 489 ``` do { ``` 490 1 ``` pi += elsize; ``` 491 1 ``` } while (cmp(pi, vp, arr) < 0 && pi < pj); ``` 492 ``` do { ``` 493 1 ``` pj -= elsize; ``` 494 1 ``` } while (cmp(vp, pj, arr) < 0 && pi < pj); ``` 495 1 ``` if (pi >= pj) { ``` 496 ``` break; ``` 497 ``` } ``` 498 ``` GENERIC_SWAP(pi, pj, elsize); ``` 499 ``` } ``` 500 ``` pk = pr - elsize; ``` 501 1 ``` GENERIC_SWAP(pi, pk, elsize); ``` 502 ``` /* push largest partition on stack */ ``` 503 1 ``` if (pi - pl < pr - pi) { ``` 504 1 ``` *sptr++ = pi + elsize; ``` 505 1 ``` *sptr++ = pr; ``` 506 1 ``` pr = pi - elsize; ``` 507 ``` } ``` 508 ``` else { ``` 509 1 ``` *sptr++ = pl; ``` 510 1 ``` *sptr++ = pi - elsize; ``` 511 1 ``` pl = pi + elsize; ``` 512 ``` } ``` 513 1 ``` *psdepth++ = --cdepth; ``` 514 ``` } ``` 515 516 ``` /* insertion sort */ ``` 517 1 ``` for (pi = pl + elsize; pi <= pr; pi += elsize) { ``` 518 1 ``` GENERIC_COPY(vp, pi, elsize); ``` 519 1 ``` pj = pi; ``` 520 1 ``` pk = pi - elsize; ``` 521 1 ``` while (pj > pl && cmp(vp, pk, arr) < 0) { ``` 522 1 ``` GENERIC_COPY(pj, pk, elsize); ``` 523 1 ``` pj -= elsize; ``` 524 1 ``` pk -= elsize; ``` 525 ``` } ``` 526 1 ``` GENERIC_COPY(pj, vp, elsize); ``` 527 ``` } ``` 528 1 ```stack_pop: ``` 529 1 ``` if (sptr == stack) { ``` 530 ``` break; ``` 531 ``` } ``` 532 1 ``` pr = *(--sptr); ``` 533 1 ``` pl = *(--sptr); ``` 534 1 ``` cdepth = *(--psdepth); ``` 535 ``` } ``` 536 537 1 ``` free(vp); ``` 538 1 ``` return 0; ``` 539 ```} ``` 540 541 542 ```NPY_NO_EXPORT int ``` 543 1 ```npy_aquicksort(void *vv, npy_intp* tosort, npy_intp num, void *varr) ``` 544 ```{ ``` 545 1 ``` char *v = vv; ``` 546 1 ``` PyArrayObject *arr = varr; ``` 547 1 ``` npy_intp elsize = PyArray_ITEMSIZE(arr); ``` 548 1 ``` PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare; ``` 549 ``` char *vp; ``` 550 1 ``` npy_intp *pl = tosort; ``` 551 1 ``` npy_intp *pr = tosort + num - 1; ``` 552 ``` npy_intp *stack[PYA_QS_STACK]; ``` 553 1 ``` npy_intp **sptr = stack; ``` 554 ``` npy_intp *pm, *pi, *pj, *pk, vi; ``` 555 ``` int depth[PYA_QS_STACK]; ``` 556 1 ``` int * psdepth = depth; ``` 557 1 ``` int cdepth = npy_get_msb(num) * 2; ``` 558 559 ``` /* Items that have zero size don't make sense to sort */ ``` 560 1 ``` if (elsize == 0) { ``` 561 ``` return 0; ``` 562 ``` } ``` 563 564 ``` for (;;) { ``` 565 1 ``` if (NPY_UNLIKELY(cdepth < 0)) { ``` 566 0 ``` npy_aheapsort(vv, pl, pr - pl + 1, varr); ``` 567 0 ``` goto stack_pop; ``` 568 ``` } ``` 569 1 ``` while ((pr - pl) > SMALL_QUICKSORT) { ``` 570 ``` /* quicksort partition */ ``` 571 1 ``` pm = pl + ((pr - pl) >> 1); ``` 572 1 ``` if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) { ``` 573 1 ``` INTP_SWAP(*pm, *pl); ``` 574 ``` } ``` 575 1 ``` if (cmp(v + (*pr)*elsize, v + (*pm)*elsize, arr) < 0) { ``` 576 1 ``` INTP_SWAP(*pr, *pm); ``` 577 ``` } ``` 578 1 ``` if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) { ``` 579 1 ``` INTP_SWAP(*pm, *pl); ``` 580 ``` } ``` 581 1 ``` vp = v + (*pm)*elsize; ``` 582 1 ``` pi = pl; ``` 583 1 ``` pj = pr - 1; ``` 584 1 ``` INTP_SWAP(*pm,*pj); ``` 585 1 ``` for (;;) { ``` 586 ``` do { ``` 587 1 ``` ++pi; ``` 588 1 ``` } while (cmp(v + (*pi)*elsize, vp, arr) < 0 && pi < pj); ``` 589 ``` do { ``` 590 1 ``` --pj; ``` 591 1 ``` } while (cmp(vp, v + (*pj)*elsize, arr) < 0 && pi < pj); ``` 592 1 ``` if (pi >= pj) { ``` 593 ``` break; ``` 594 ``` } ``` 595 1 ``` INTP_SWAP(*pi,*pj); ``` 596 ``` } ``` 597 1 ``` pk = pr - 1; ``` 598 1 ``` INTP_SWAP(*pi,*pk); ``` 599 ``` /* push largest partition on stack */ ``` 600 1 ``` if (pi - pl < pr - pi) { ``` 601 1 ``` *sptr++ = pi + 1; ``` 602 1 ``` *sptr++ = pr; ``` 603 1 ``` pr = pi - 1; ``` 604 ``` } ``` 605 ``` else { ``` 606 1 ``` *sptr++ = pl; ``` 607 1 ``` *sptr++ = pi - 1; ``` 608 1 ``` pl = pi + 1; ``` 609 ``` } ``` 610 1 ``` *psdepth++ = --cdepth; ``` 611 ``` } ``` 612 613 ``` /* insertion sort */ ``` 614 1 ``` for (pi = pl + 1; pi <= pr; ++pi) { ``` 615 1 ``` vi = *pi; ``` 616 1 ``` vp = v + vi*elsize; ``` 617 1 ``` pj = pi; ``` 618 1 ``` pk = pi - 1; ``` 619 1 ``` while (pj > pl && cmp(vp, v + (*pk)*elsize, arr) < 0) { ``` 620 1 ``` *pj-- = *pk--; ``` 621 ``` } ``` 622 1 ``` *pj = vi; ``` 623 ``` } ``` 624 1 ```stack_pop: ``` 625 1 ``` if (sptr == stack) { ``` 626 ``` break; ``` 627 ``` } ``` 628 1 ``` pr = *(--sptr); ``` 629 1 ``` pl = *(--sptr); ``` 630 1 ``` cdepth = *(--psdepth); ``` 631 ``` } ``` 632 633 ``` return 0; ``` 634 ```} ```

Read our documentation on viewing source code .