MAINT: refactor PyArray_Sort and PyArray_Partition

Modified the generic sort functions, npy_quicksort, npy_heapsort
and npy_mergesort, to have a signature compatible with the other
sort functions. Got rid of the global compare ugliness, and
refactored PyArray_Sort and PyArray_Partition to use the new
functions through a call to _new_sortlike.

9 files changed, 198 insertions, 378 deletions

diff --git a/numpy/core/src/multiarray/item_selection.c b/numpy/core/src/multiarray/item_selection.c
index e2ef8efdd..0d9474be3 100644
--- a/numpy/core/src/multiarray/item_selection.c
+++ b/numpy/core/src/multiarray/item_selection.c
@@ -1093,87 +1093,20 @@ fail:
 }
 
 
-/* Be sure to save this global_compare when necessary */
-static PyArrayObject *global_obj;
-
-static int
-sortCompare (const void *a, const void *b)
-{
-    return PyArray_DESCR(global_obj)->f->compare(a,b,global_obj);
-}
-
-/*
- * Consumes reference to ap (op gets it) op contains a version of
- * the array with axes swapped if local variable axis is not the
- * last dimension.  Origin must be defined locally.
- */
-#define SWAPAXES(op, ap) { \
-        orign = PyArray_NDIM(ap)-1; \
-        if (axis != orign) { \
-            (op) = (PyArrayObject *)PyArray_SwapAxes((ap), axis, orign); \
-            Py_DECREF((ap)); \
-            if ((op) == NULL) return NULL; \
-        } \
-        else (op) = (ap); \
-    }
-
-/*
- * Consumes reference to ap (op gets it) origin must be previously
- * defined locally.  SWAPAXES must have been called previously.
- * op contains the swapped version of the array.
- */
-#define SWAPBACK(op, ap) {                                      \
-        if (axis != orign) {                                    \
-            (op) = (PyArrayObject *)PyArray_SwapAxes((ap), axis, orign); \
-            Py_DECREF((ap));                                    \
-            if ((op) == NULL) return NULL;                      \
-        }                                                       \
-        else (op) = (ap);                                       \
-    }
-
-/* These swap axes in-place if necessary */
-#define SWAPINTP(a,b) {npy_intp c; c=(a); (a) = (b); (b) = c;}
-#define SWAPAXES2(ap) { \
-        orign = PyArray_NDIM(ap)-1; \
-        if (axis != orign) { \
-            SWAPINTP(PyArray_DIMS(ap)[axis], PyArray_DIMS(ap)[orign]); \
-            SWAPINTP(PyArray_STRIDES(ap)[axis], PyArray_STRIDES(ap)[orign]); \
-            PyArray_UpdateFlags(ap, NPY_ARRAY_C_CONTIGUOUS | \
-                                    NPY_ARRAY_F_CONTIGUOUS); \
-        } \
-    }
-
-#define SWAPBACK2(ap) { \
-        if (axis != orign) { \
-            SWAPINTP(PyArray_DIMS(ap)[axis], PyArray_DIMS(ap)[orign]); \
-            SWAPINTP(PyArray_STRIDES(ap)[axis], PyArray_STRIDES(ap)[orign]); \
-            PyArray_UpdateFlags(ap, NPY_ARRAY_C_CONTIGUOUS | \
-                                    NPY_ARRAY_F_CONTIGUOUS); \
-        } \
-    }
-
 /*NUMPY_API
  * Sort an array in-place
  */
 NPY_NO_EXPORT int
 PyArray_Sort(PyArrayObject *op, int axis, NPY_SORTKIND which)
 {
-    PyArrayObject *ap = NULL, *store_arr = NULL;
-    char *ip;
-    npy_intp i, n, m;
-    int elsize, orign;
-    int res = 0;
+    PyArray_SortFunc *sort;
     int axis_orig = axis;
-    int (*sort)(void *, size_t, size_t, npy_comparator);
+    int  n = PyArray_NDIM(op);
 
-    n = PyArray_NDIM(op);
-    if ((n == 0) || (PyArray_SIZE(op) == 1)) {
-        return 0;
-    }
     if (axis < 0) {
         axis += n;
     }
-    if ((axis < 0) || (axis >= n)) {
+    if (axis < 0 || axis >= n) {
         PyErr_Format(PyExc_ValueError, "axis(=%d) out of bounds", axis_orig);
         return -1;
     }
@@ -1181,83 +1114,35 @@ PyArray_Sort(PyArrayObject *op, int axis, NPY_SORTKIND which)
         return -1;
     }
 
-    /* Determine if we should use type-specific algorithm or not */
-    if (PyArray_DESCR(op)->f->sort[which] != NULL) {
-        return _new_sortlike(op, axis, PyArray_DESCR(op)->f->sort[which],
-                             NULL, NULL, 0);
-    }
-
-    if (PyArray_DESCR(op)->f->compare == NULL) {
-        PyErr_SetString(PyExc_TypeError,
-                "type does not have compare function");
+    if (which < 0 || which >= NPY_NSORTS) {
+        PyErr_SetString(PyExc_ValueError, "not a valid sort kind");
         return -1;
     }
 
-    SWAPAXES2(op);
-
-    switch (which) {
-        case NPY_QUICKSORT :
-            sort = npy_quicksort;
-            break;
-        case NPY_HEAPSORT :
-            sort = npy_heapsort;
-            break;
-        case NPY_MERGESORT :
-            sort = npy_mergesort;
-            break;
-        default:
+    sort = PyArray_DESCR(op)->f->sort[which];
+    if (sort == NULL) {
+        if (PyArray_DESCR(op)->f->compare) {
+            switch (which) {
+                default:
+                case NPY_QUICKSORT:
+                    sort = npy_quicksort;
+                    break;
+                case NPY_HEAPSORT:
+                    sort = npy_heapsort;
+                    break;
+                case NPY_MERGESORT:
+                    sort = npy_mergesort;
+                    break;
+            }
+        }
+        else {
             PyErr_SetString(PyExc_TypeError,
-                    "requested sort kind is not supported");
-            goto fail;
-    }
-
-    ap = (PyArrayObject *)PyArray_FromAny((PyObject *)op,
-                          NULL, 1, 0,
-                          NPY_ARRAY_DEFAULT | NPY_ARRAY_UPDATEIFCOPY, NULL);
-    if (ap == NULL) {
-        goto fail;
-    }
-    elsize = PyArray_DESCR(ap)->elsize;
-    m = PyArray_DIMS(ap)[PyArray_NDIM(ap)-1];
-    if (m == 0) {
-        goto finish;
-    }
-    n = PyArray_SIZE(ap)/m;
-
-    /* Store global -- allows re-entry -- restore before leaving*/
-    store_arr = global_obj;
-    global_obj = ap;
-    for (ip = PyArray_DATA(ap), i = 0; i < n; i++, ip += elsize*m) {
-        res = sort(ip, m, elsize, sortCompare);
-        if (res < 0) {
-            break;
+                            "type does not have compare function");
+            return -1;
         }
     }
-    global_obj = store_arr;
 
-    if (PyErr_Occurred()) {
-        goto fail;
-    }
-    else if (res == -NPY_ENOMEM) {
-        PyErr_NoMemory();
-        goto fail;
-    }
-    else if (res == -NPY_ECOMP) {
-        PyErr_SetString(PyExc_TypeError,
-                "sort comparison failed");
-        goto fail;
-    }
-
-
- finish:
-    Py_DECREF(ap);  /* Should update op if needed */
-    SWAPBACK2(op);
-    return 0;
-
- fail:
-    Py_XDECREF(ap);
-    SWAPBACK2(op);
-    return -1;
+    return _new_sortlike(op, axis, sort, NULL, NULL, 0);
 }
 
 
@@ -1297,7 +1182,8 @@ partition_prep_kth_array(PyArrayObject * ktharray,
         if (kth[i] < 0) {
             kth[i] += shape[axis];
         }
-        if (PyArray_SIZE(op) != 0 && ((kth[i] < 0) || (kth[i] >= shape[axis]))) {
+        if (PyArray_SIZE(op) != 0 &&
+                    (kth[i] < 0 || kth[i] >= shape[axis])) {
             PyErr_Format(PyExc_ValueError, "kth(=%zd) out of bounds (%zd)",
                          kth[i], shape[axis]);
             Py_XDECREF(kthrvl);
@@ -1309,124 +1195,68 @@ partition_prep_kth_array(PyArrayObject * ktharray,
      * sort the array of kths so the partitions will
      * not trample on each other
      */
-    PyArray_Sort(kthrvl, -1, NPY_QUICKSORT);
+    if (PyArray_SIZE(kthrvl) > 1) {
+        PyArray_Sort(kthrvl, -1, NPY_QUICKSORT);
+    }
 
     return kthrvl;
 }
 
 
-
 /*NUMPY_API
  * Partition an array in-place
  */
 NPY_NO_EXPORT int
-PyArray_Partition(PyArrayObject *op, PyArrayObject * ktharray, int axis, NPY_SELECTKIND which)
+PyArray_Partition(PyArrayObject *op, PyArrayObject * ktharray, int axis,
+                  NPY_SELECTKIND which)
 {
-    PyArrayObject *ap = NULL, *store_arr = NULL;
-    char *ip;
-    npy_intp i, n, m;
-    int elsize, orign;
-    int res = 0;
+    PyArrayObject *kthrvl;
+    PyArray_PartitionFunc *part;
+    PyArray_SortFunc *sort;
     int axis_orig = axis;
-    int (*sort)(void *, size_t, size_t, npy_comparator);
-    PyArray_PartitionFunc * part = get_partition_func(PyArray_TYPE(op), which);
+    int n = PyArray_NDIM(op);
+    int ret;
 
-    n = PyArray_NDIM(op);
-    if (n == 0) {
-        return 0;
-    }
     if (axis < 0) {
         axis += n;
     }
-    if ((axis < 0) || (axis >= n)) {
+    if (axis < 0 || axis >= n) {
         PyErr_Format(PyExc_ValueError, "axis(=%d) out of bounds", axis_orig);
         return -1;
     }
-    if (PyArray_FailUnlessWriteable(op, "sort array") < 0) {
+    if (PyArray_FailUnlessWriteable(op, "partition array") < 0) {
         return -1;
     }
 
-    if (part) {
-        PyArrayObject * kthrvl = partition_prep_kth_array(ktharray, op, axis);
-        if (kthrvl == NULL)
-            return -1;
-
-        res = _new_sortlike(op, axis, NULL,
-                            part,
-                            PyArray_DATA(kthrvl),
-                            PyArray_SIZE(kthrvl));
-        Py_DECREF(kthrvl);
-        return res;
-    }
-
-
-    if (PyArray_DESCR(op)->f->compare == NULL) {
-        PyErr_SetString(PyExc_TypeError,
-                "type does not have compare function");
-        return -1;
+    if (which < 0 || which >= NPY_NSELECTS) {
+        PyErr_SetString(PyExc_ValueError, "not a valid partition kind");
+        return NULL;
     }
-
-    SWAPAXES2(op);
-
-    /* select not implemented, use quicksort, slower but equivalent */
-    switch (which) {
-        case NPY_INTROSELECT :
+    part = get_partition_func(PyArray_TYPE(op), which);
+    if (part == NULL) {
+        /* Use sorting, slower but equivalent */
+        if (PyArray_DESCR(op)->f->compare) {
             sort = npy_quicksort;
-            break;
-        default:
+        }
+        else {
             PyErr_SetString(PyExc_TypeError,
-                    "requested sort kind is not supported");
-            goto fail;
-    }
-
-    ap = (PyArrayObject *)PyArray_FromAny((PyObject *)op,
-                          NULL, 1, 0,
-                          NPY_ARRAY_DEFAULT | NPY_ARRAY_UPDATEIFCOPY, NULL);
-    if (ap == NULL) {
-        goto fail;
-    }
-    elsize = PyArray_DESCR(ap)->elsize;
-    m = PyArray_DIMS(ap)[PyArray_NDIM(ap)-1];
-    if (m == 0) {
-        goto finish;
-    }
-    n = PyArray_SIZE(ap)/m;
-
-    /* Store global -- allows re-entry -- restore before leaving*/
-    store_arr = global_obj;
-    global_obj = ap;
-    /* we don't need to care about kth here as we are using a full sort */
-    for (ip = PyArray_DATA(ap), i = 0; i < n; i++, ip += elsize*m) {
-        res = sort(ip, m, elsize, sortCompare);
-        if (res < 0) {
-            break;
+                            "type does not have compare function");
+            return NULL;
         }
     }
-    global_obj = store_arr;
 
-    if (PyErr_Occurred()) {
-        goto fail;
-    }
-    else if (res == -NPY_ENOMEM) {
-        PyErr_NoMemory();
-        goto fail;
-    }
-    else if (res == -NPY_ECOMP) {
-        PyErr_SetString(PyExc_TypeError,
-                "sort comparison failed");
-        goto fail;
+    /* Process ktharray even if using sorting to do bounds checking */
+    kthrvl = partition_prep_kth_array(ktharray, op, axis);
+    if (kthrvl == NULL) {
+        return -1;
     }
 
+    ret = _new_sortlike(op, axis, sort, part,
+                        PyArray_DATA(kthrvl), PyArray_SIZE(kthrvl));
 
- finish:
-    Py_DECREF(ap);  /* Should update op if needed */
-    SWAPBACK2(op);
-    return 0;
+    Py_DECREF(kthrvl);
 
- fail:
-    Py_XDECREF(ap);
-    SWAPBACK2(op);
-    return -1;
+    return ret;
 }
 
 
diff --git a/numpy/core/src/npysort/heapsort.c.src b/numpy/core/src/npysort/heapsort.c.src
index bec8cc032..88f7978cc 100644
--- a/numpy/core/src/npysort/heapsort.c.src
+++ b/numpy/core/src/npysort/heapsort.c.src
@@ -287,30 +287,27 @@ aheapsort_@suff@(@type@ *v, npy_intp *tosort, npy_intp n, PyArrayObject *arr)
  */
 
 
-/*
- * This sort has almost the same signature as libc qsort and is intended to
- * provide a heapsort for array types that don't have type specific sorts.
- * The difference in the signature is an error return, as it might be the
- * case that a memory allocation fails.
- */
 int
-npy_heapsort(void *base, size_t num, size_t size, npy_comparator cmp)
+npy_heapsort(char *start, npy_intp num, PyArrayObject *arr)
 {
-    char *tmp = malloc(size);
-    char *a = (char *) base - size;
-    size_t i, j, l;
+    npy_intp elsize = PyArray_ITEMSIZE(arr);
+    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
+    char *tmp = malloc(elsize);
+    char *a = start - elsize;
+    npy_intp i, j, l;
 
     if (tmp == NULL) {
         return -NPY_ENOMEM;
     }
 
     for (l = num >> 1; l > 0; --l) {
-        GENERIC_COPY(tmp, a + l*size, size);
+        GENERIC_COPY(tmp, a + l*elsize, elsize);
         for (i = l, j = l << 1; j <= num;) {
-            if (j < num && GENERIC_LT(a + j*size, a + (j+1)*size, cmp))
-                j += 1;
-            if (GENERIC_LT(tmp, a + j*size, cmp)) {
-                GENERIC_COPY(a + i*size, a + j*size, size);
+            if (j < num && cmp(a + j*elsize, a + (j+1)*elsize, arr) < 0) {
+                ++j;
+            }
+            if (cmp(tmp, a + j*elsize, arr) < 0) {
+                GENERIC_COPY(a + i*elsize, a + j*elsize, elsize);
                 i = j;
                 j += j;
             }
@@ -318,18 +315,19 @@ npy_heapsort(void *base, size_t num, size_t size, npy_comparator cmp)
                 break;
             }
         }
-        GENERIC_COPY(a + i*size, tmp, size);
+        GENERIC_COPY(a + i*elsize, tmp, elsize);
     }
 
     for (; num > 1;) {
-        GENERIC_COPY(tmp, a + num*size, size);
-        GENERIC_COPY(a + num*size, a + size, size);
+        GENERIC_COPY(tmp, a + num*elsize, elsize);
+        GENERIC_COPY(a + num*elsize, a + elsize, elsize);
         num -= 1;
         for (i = 1, j = 2; j <= num;) {
-            if (j < num && GENERIC_LT(a + j*size, a + (j+1)*size, cmp))
-                j++;
-            if (GENERIC_LT(tmp, a + j*size, cmp)) {
-                GENERIC_COPY(a + i*size, a + j*size, size);
+            if (j < num && cmp(a + j*elsize, a + (j+1)*elsize, arr) < 0) {
+                ++j;
+            }
+            if (cmp(tmp, a + j*elsize, arr) < 0) {
+                GENERIC_COPY(a + i*elsize, a + j*elsize, elsize);
                 i = j;
                 j += j;
             }
@@ -337,7 +335,7 @@ npy_heapsort(void *base, size_t num, size_t size, npy_comparator cmp)
                 break;
             }
         }
-        GENERIC_COPY(a + i*size, tmp, size);
+        GENERIC_COPY(a + i*elsize, tmp, elsize);
     }
 
     free(tmp);
diff --git a/numpy/core/src/npysort/mergesort.c.src b/numpy/core/src/npysort/mergesort.c.src
index ecf39720a..406be66d0 100644
--- a/numpy/core/src/npysort/mergesort.c.src
+++ b/numpy/core/src/npysort/mergesort.c.src
@@ -350,80 +350,70 @@ amergesort_@suff@(@type@ *v, npy_intp *tosort, npy_intp num, PyArrayObject *arr)
 
 
 static void
-npy_mergesort0(char *pl, char *pr, char *pw, char *vp, size_t size, npy_comparator cmp)
+npy_mergesort0(char *pl, char *pr, char *pw, char *vp, npy_intp elsize,
+               PyArray_CompareFunc *cmp, PyArrayObject *arr)
 {
     char *pi, *pj, *pk, *pm;
 
-    if ((size_t)(pr - pl) > SMALL_MERGESORT*size) {
+    if (pr - pl > SMALL_MERGESORT*elsize) {
         /* merge sort */
-        pm = pl + (((pr - pl)/size) >> 1)*size;
-        npy_mergesort0(pl, pm, pw, vp, size, cmp);
-        npy_mergesort0(pm, pr, pw, vp, size, cmp);
+        pm = pl + (((pr - pl)/elsize) >> 1)*elsize;
+        npy_mergesort0(pl, pm, pw, vp, elsize, cmp, arr);
+        npy_mergesort0(pm, pr, pw, vp, elsize, cmp, arr);
         GENERIC_COPY(pw, pl, pm - pl);
         pi = pw + (pm - pl);
         pj = pw;
         pk = pl;
         while (pj < pi && pm < pr) {
-            if (GENERIC_LT(pm, pj, cmp)) {
-                GENERIC_COPY(pk, pm, size);
-                pm += size;
-                pk += size;
+            if (cmp(pm, pj, arr) < 0) {
+                GENERIC_COPY(pk, pm, elsize);
+                pm += elsize;
+                pk += elsize;
             }
             else {
-                GENERIC_COPY(pk, pj, size);
-                pj += size;
-                pk += size;
+                GENERIC_COPY(pk, pj, elsize);
+                pj += elsize;
+                pk += elsize;
             }
         }
         GENERIC_COPY(pk, pj, pi - pj);
     }
     else {
         /* insertion sort */
-        for (pi = pl + size; pi < pr; pi += size) {
-            GENERIC_COPY(vp, pi, size);
+        for (pi = pl + elsize; pi < pr; pi += elsize) {
+            GENERIC_COPY(vp, pi, elsize);
             pj = pi;
-            pk = pi - size;
-            while (pj > pl && GENERIC_LT(vp, pk, cmp)) {
-                GENERIC_COPY(pj, pk, size);
-                pj -= size;
-                pk -= size;
+            pk = pi - elsize;
+            while (pj > pl && cmp(vp, pk, arr) < 0) {
+                GENERIC_COPY(pj, pk, elsize);
+                pj -= elsize;
+                pk -= elsize;
             }
-            GENERIC_COPY(pj, vp, size);
+            GENERIC_COPY(pj, vp, elsize);
         }
     }
 }
 
 
-/*
- * This sort has almost the same signature as libc qsort and is intended to
- * provide a mergesort for array types that don't have type specific sorts.
- * The difference in the signature is an error return, as it might be the
- * case that a memory allocation fails.
- */
 int
-npy_mergesort(void *base, size_t num, size_t size, npy_comparator cmp)
+npy_mergesort(char *start, npy_intp num, PyArrayObject *arr)
 {
-    char *pl, *pr, *pw, *vp;
-    int err = 0;
-
-    pl = base;
-    pr = pl + num*size;
-    pw = malloc((num/2) * size);
-    if (pw == NULL) {
-        err = -NPY_ENOMEM;
-        goto fail_0;
-    }
-    vp = malloc(size);
-    if (vp == NULL) {
-        err = -NPY_ENOMEM;
-        goto fail_1;
+    npy_intp elsize = PyArray_ITEMSIZE(arr);
+    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
+    char *pl = start;
+    char *pr = pl + num*elsize;
+    char *pw = malloc((num >> 1) *elsize);
+    char *vp = malloc(elsize);
+    int err = -NPY_ENOMEM;
+
+    if (pw != NULL && vp != NULL) {
+        npy_mergesort0(pl, pr, pw, vp, elsize, cmp, arr);
+        err = 0;
     }
-    npy_mergesort0(pl, pr, pw, vp, size, cmp);
 
     free(vp);
-fail_1:
     free(pw);
-fail_0:
+
     return err;
 }
 
diff --git a/numpy/core/src/npysort/npysort_common.h b/numpy/core/src/npysort/npysort_common.h
index a3ce7664d..a22045b41 100644
--- a/numpy/core/src/npysort/npysort_common.h
+++ b/numpy/core/src/npysort/npysort_common.h
@@ -357,11 +357,4 @@ GENERIC_SWAP(char *a, char *b, size_t len)
     }
 }
 
-
-NPY_INLINE static int
-GENERIC_LT(char *a, char *b, int (*cmp)(const void *, const void *))
-{
-    return cmp(a, b) < 0;
-}
-
 #endif
diff --git a/numpy/core/src/npysort/quicksort.c.src b/numpy/core/src/npysort/quicksort.c.src
index fcde70957..5334aca76 100644
--- a/numpy/core/src/npysort/quicksort.c.src
+++ b/numpy/core/src/npysort/quicksort.c.src
@@ -216,6 +216,10 @@ quicksort_@suff@(@type@ *start, npy_intp num, PyArrayObject *arr)
     @type@ *pr = start + (num - 1)*len;
     @type@ *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk;
 
+    if (vp == NULL) {
+        return -NPY_ENOMEM;
+    }
+
     for (;;) {
         while ((size_t)(pr - pl) > SMALL_QUICKSORT*len) {
             /* quicksort partition */
@@ -350,15 +354,86 @@ aquicksort_@suff@(@type@ *v, npy_intp* tosort, npy_intp num, PyArrayObject *arr)
  */
 
 
-/*
- * This sort has almost the same signature as libc qsort and is intended to
- * supply an error return for compatibility with the other generic sort
- * kinds.
- */
 int
-npy_quicksort(void *base, size_t num, size_t size, npy_comparator cmp)
+npy_quicksort(char *start, npy_intp num, PyArrayObject *arr)
 {
-    qsort(base, num, size, cmp);
+    npy_intp elsize = PyArray_ITEMSIZE(arr);
+    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
+    char *vp = malloc(elsize);
+    char *pl = start;
+    char *pr = start + (num - 1)*elsize;
+    char *stack[PYA_QS_STACK];
+    char **sptr = stack;
+    char *pm, *pi, *pj, *pk;
+
+    if (vp == NULL) {
+        return -NPY_ENOMEM;
+    }
+
+    for (;;) {
+        while(pr - pl > SMALL_QUICKSORT*elsize) {
+            /* quicksort partition */
+            pm = pl + (((pr - pl) / elsize) >> 1) * elsize;
+            if (cmp(pm, pl, arr) < 0) {
+                GENERIC_SWAP(pm, pl, elsize);
+            }
+            if (cmp(pr, pm, arr) < 0) {
+                GENERIC_SWAP(pr, pm, elsize);
+            }
+            if (cmp(pm, pl, arr) < 0) {
+                GENERIC_SWAP(pm, pl, elsize);
+            }
+            GENERIC_COPY(vp, pm, elsize);
+            pi = pl;
+            pj = pr - elsize;
+            GENERIC_SWAP(pm, pj, elsize);
+            for (;;) {
+                do {
+                    pi += elsize;
+                } while (cmp(pi, vp, arr) < 0);
+                do {
+                    pj -= elsize;
+                } while (cmp(vp, pj, arr) < 0);
+                if (pi >= pj) {
+                    break;
+                }
+                GENERIC_SWAP(pi, pj, elsize);
+            }
+            pk = pr - elsize;
+            GENERIC_SWAP(pi, pk, elsize);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + elsize;
+                *sptr++ = pr;
+                pr = pi - elsize;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - elsize;
+                pl = pi + elsize;
+            }
+        }
+
+        /* insertion sort */
+        for (pi = pl + elsize; pi <= pr; pi += elsize) {
+            GENERIC_COPY(vp, pi, elsize);
+            pj = pi;
+            pk = pi - elsize;
+            while (pj > pl && cmp(vp, pk, arr) < 0) {
+                GENERIC_COPY(pj, pk, elsize);
+                pj -= elsize;
+                pk -= elsize;
+            }
+            GENERIC_COPY(pj, vp, elsize);
+        }
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+    }
+
+    free(vp);
     return 0;
 }
 
diff --git a/numpy/core/src/npysort/selection.c.src b/numpy/core/src/npysort/selection.c.src
index 4167b2694..51c7d6721 100644
--- a/numpy/core/src/npysort/selection.c.src
+++ b/numpy/core/src/npysort/selection.c.src
@@ -424,51 +424,3 @@ int
 /**end repeat1**/
 
 /**end repeat**/
-
-
-/*
- *****************************************************************************
- **                             STRING SORTS                                **
- *****************************************************************************
- */
-
-
-/**begin repeat
- *
- * #TYPE = STRING, UNICODE#
- * #suff = string, unicode#
- * #type = npy_char, npy_ucs4#
- */
-
-int
-introselect_@suff@(@type@ *start, npy_intp num, npy_intp kth, PyArrayObject *arr)
-{
-    return quicksort_@suff@(start, num, arr);
-}
-
-int
-aintroselect_@suff@(@type@ *v, npy_intp* tosort, npy_intp num, npy_intp kth, void *null)
-{
-    return aquicksort_@suff@(v, tosort, num, null);
-}
-
-/**end repeat**/
-
-
-/*
- *****************************************************************************
- **                             GENERIC SORT                                **
- *****************************************************************************
- */
-
-
-/*
- * This sort has almost the same signature as libc qsort and is intended to
- * supply an error return for compatibility with the other generic sort
- * kinds.
- */
-int
-npy_introselect(void *base, size_t num, size_t size, size_t kth, npy_comparator cmp)
-{
-    return npy_quicksort(base, num, size, cmp);
-}
diff --git a/numpy/core/src/private/npy_partition.h.src b/numpy/core/src/private/npy_partition.h.src
index fd79068f7..07aecd4f8 100644
--- a/numpy/core/src/private/npy_partition.h.src
+++ b/numpy/core/src/private/npy_partition.h.src
@@ -55,22 +55,6 @@ NPY_VISIBILITY_HIDDEN int aintroselect_@suff@(@type@ *v, npy_intp* tosort, npy_i
 
 /**end repeat**/
 
-NPY_VISIBILITY_HIDDEN int introselect_string(npy_char *vec, npy_intp cnt,
-                                             npy_intp kth, PyArrayObject *arr);
-NPY_VISIBILITY_HIDDEN int aintroselect_string(npy_char *vec, npy_intp *ind,
-                                              npy_intp cnt, npy_intp kth,
-                                              void *null);
-
-
-NPY_VISIBILITY_HIDDEN int introselect_unicode(npy_ucs4 *vec, npy_intp cnt,
-                                              npy_intp kth, PyArrayObject *arr);
-NPY_VISIBILITY_HIDDEN int aintroselect_unicode(npy_ucs4 *vec, npy_intp *ind,
-                                               npy_intp cnt, npy_intp kth,
-                                               void *null);
-
-NPY_VISIBILITY_HIDDEN int npy_introselect(void *base, size_t num, size_t size,
-                                          size_t kth, npy_comparator cmp);
-
 typedef struct {
     enum NPY_TYPES typenum;
     PyArray_PartitionFunc * part[NPY_NSELECTS];
diff --git a/numpy/core/src/private/npy_sort.h b/numpy/core/src/private/npy_sort.h
index 7c5701f88..85630b2df 100644
--- a/numpy/core/src/private/npy_sort.h
+++ b/numpy/core/src/private/npy_sort.h
@@ -9,7 +9,6 @@
 #define NPY_ENOMEM 1
 #define NPY_ECOMP 2
 
-typedef int (*npy_comparator)(const void *, const void *);
 
 int quicksort_bool(npy_bool *vec, npy_intp cnt, void *null);
 int heapsort_bool(npy_bool *vec, npy_intp cnt, void *null);
@@ -187,9 +186,9 @@ int aheapsort_timedelta(npy_timedelta *vec, npy_intp *ind, npy_intp cnt, void *n
 int amergesort_timedelta(npy_timedelta *vec, npy_intp *ind, npy_intp cnt, void *null);
 
 
-int npy_quicksort(void *base, size_t num, size_t size, npy_comparator cmp);
-int npy_heapsort(void *base, size_t num, size_t size, npy_comparator cmp);
-int npy_mergesort(void *base, size_t num, size_t size, npy_comparator cmp);
+int npy_quicksort(char *vec, npy_intp cnt, PyArrayObject *arr);
+int npy_heapsort(char *vec, npy_intp cnt, PyArrayObject *arr);
+int npy_mergesort(char *vec, npy_intp cnt, PyArrayObject *arr);
 int npy_aquicksort(char *vec, npy_intp *ind, npy_intp cnt, PyArrayObject *arr);
 int npy_aheapsort(char *vec, npy_intp *ind, npy_intp cnt, PyArrayObject *arr);
 int npy_amergesort(char *vec, npy_intp *ind, npy_intp cnt, PyArrayObject *arr);
diff --git a/numpy/core/tests/test_multiarray.py b/numpy/core/tests/test_multiarray.py
index 0c13cff6a..08ba320e5 100644
--- a/numpy/core/tests/test_multiarray.py
+++ b/numpy/core/tests/test_multiarray.py
@@ -1436,7 +1436,6 @@ class TestMethods(TestCase):
         assert_raises(ValueError, d_obj.argpartition, 10)
         assert_raises(ValueError, d_obj.argpartition, -11)
 
-    @dec.knownfailureif(True, "Ticket #5469 fixed for argpartition only")
     def test_partition_out_of_range(self):
         # Test out of range values in kth raise an error, gh-5469
         d = np.arange(10)