| 50 | */ |
| 51 | |
| 52 | NPY_NO_EXPORT int |
| 53 | npy_heapsort(void *start, npy_intp num, void *varr) |
| 54 | { |
| 55 | PyArrayObject *arr = (PyArrayObject *)varr; |
| 56 | npy_intp elsize = PyArray_ITEMSIZE(arr); |
| 57 | PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare; |
| 58 | if (elsize == 0) { |
| 59 | return 0; /* no need for sorting elements of no size */ |
| 60 | } |
| 61 | char *tmp = (char *)malloc(elsize); |
| 62 | char *a = (char *)start - elsize; |
| 63 | npy_intp i, j, l; |
| 64 | |
| 65 | if (tmp == NULL) { |
| 66 | return -NPY_ENOMEM; |
| 67 | } |
| 68 | |
| 69 | for (l = num >> 1; l > 0; --l) { |
| 70 | GENERIC_COPY(tmp, a + l * elsize, elsize); |
| 71 | for (i = l, j = l << 1; j <= num;) { |
| 72 | if (j < num && |
| 73 | cmp(a + j * elsize, a + (j + 1) * elsize, arr) < 0) { |
| 74 | ++j; |
| 75 | } |
| 76 | if (cmp(tmp, a + j * elsize, arr) < 0) { |
| 77 | GENERIC_COPY(a + i * elsize, a + j * elsize, elsize); |
| 78 | i = j; |
| 79 | j += j; |
| 80 | } |
| 81 | else { |
| 82 | break; |
| 83 | } |
| 84 | } |
| 85 | GENERIC_COPY(a + i * elsize, tmp, elsize); |
| 86 | } |
| 87 | |
| 88 | for (; num > 1;) { |
| 89 | GENERIC_COPY(tmp, a + num * elsize, elsize); |
| 90 | GENERIC_COPY(a + num * elsize, a + elsize, elsize); |
| 91 | num -= 1; |
| 92 | for (i = 1, j = 2; j <= num;) { |
| 93 | if (j < num && |
| 94 | cmp(a + j * elsize, a + (j + 1) * elsize, arr) < 0) { |
| 95 | ++j; |
| 96 | } |
| 97 | if (cmp(tmp, a + j * elsize, arr) < 0) { |
| 98 | GENERIC_COPY(a + i * elsize, a + j * elsize, elsize); |
| 99 | i = j; |
| 100 | j += j; |
| 101 | } |
| 102 | else { |
| 103 | break; |
| 104 | } |
| 105 | } |
| 106 | GENERIC_COPY(a + i * elsize, tmp, elsize); |
| 107 | } |
| 108 | |
| 109 | free(tmp); |
no test coverage detected