Merge pull request #20897 from serge-sans-paille/feature/road-to-cxx-quicksort

Road to C++: quicksort.c.src -> quicksort.cpp

5 files changed, 1100 insertions, 660 deletions

diff --git a/numpy/core/setup.py b/numpy/core/setup.py
index d002377c6..c5465196f 100644
--- a/numpy/core/setup.py
+++ b/numpy/core/setup.py
@@ -949,7 +949,7 @@ def configuration(parent_package='',top_path=None):
             join('src', 'multiarray', 'vdot.c'),
             join('src', 'common', 'npy_sort.h.src'),
             join('src', 'npysort', 'x86-qsort.dispatch.c.src'),
-            join('src', 'npysort', 'quicksort.c.src'),
+            join('src', 'npysort', 'quicksort.cpp'),
             join('src', 'npysort', 'mergesort.cpp'),
             join('src', 'npysort', 'timsort.cpp'),
             join('src', 'npysort', 'heapsort.cpp'),
diff --git a/numpy/core/src/npysort/heapsort.cpp b/numpy/core/src/npysort/heapsort.cpp
index 3893bf5c2..1f31ed20a 100644
--- a/numpy/core/src/npysort/heapsort.cpp
+++ b/numpy/core/src/npysort/heapsort.cpp
@@ -47,7 +47,7 @@
  */
 
 template <typename Tag, typename type>
-static int
+NPY_NO_EXPORT int
 heapsort_(type *start, npy_intp n)
 {
     type tmp, *a;
@@ -98,7 +98,7 @@ heapsort_(type *start, npy_intp n)
 }
 
 template <typename Tag, typename type>
-static int
+NPY_NO_EXPORT int
 aheapsort_(type *vv, npy_intp *tosort, npy_intp n)
 {
     type *v = vv;
@@ -382,212 +382,349 @@ npy_aheapsort(void *vv, npy_intp *tosort, npy_intp n, void *varr)
 /***************************************
  * C > C++ dispatch
  ***************************************/
-
+template NPY_NO_EXPORT int
+heapsort_<npy::bool_tag, npy_bool>(npy_bool *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_bool(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::bool_tag>((npy_bool *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::byte_tag, npy_byte>(npy_byte *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_byte(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::byte_tag>((npy_byte *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::ubyte_tag, npy_ubyte>(npy_ubyte *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_ubyte(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::ubyte_tag>((npy_ubyte *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::short_tag, npy_short>(npy_short *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_short(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::short_tag>((npy_short *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::ushort_tag, npy_ushort>(npy_ushort *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_ushort(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::ushort_tag>((npy_ushort *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::int_tag, npy_int>(npy_int *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_int(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::int_tag>((npy_int *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::uint_tag, npy_uint>(npy_uint *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_uint(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::uint_tag>((npy_uint *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::long_tag, npy_long>(npy_long *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_long(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::long_tag>((npy_long *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::ulong_tag, npy_ulong>(npy_ulong *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_ulong(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::ulong_tag>((npy_ulong *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::longlong_tag, npy_longlong>(npy_longlong *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_longlong(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::longlong_tag>((npy_longlong *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::ulonglong_tag, npy_ulonglong>(npy_ulonglong *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_ulonglong(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::ulonglong_tag>((npy_ulonglong *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::half_tag, npy_half>(npy_half *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_half(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::half_tag>((npy_half *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::float_tag, npy_float>(npy_float *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_float(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::float_tag>((npy_float *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::double_tag, npy_double>(npy_double *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_double(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::double_tag>((npy_double *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::longdouble_tag, npy_longdouble>(npy_longdouble *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_longdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::longdouble_tag>((npy_longdouble *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::cfloat_tag, npy_cfloat>(npy_cfloat *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_cfloat(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::cfloat_tag>((npy_cfloat *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::cdouble_tag, npy_cdouble>(npy_cdouble *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_cdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::cdouble_tag>((npy_cdouble *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::clongdouble_tag, npy_clongdouble>(npy_clongdouble *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_clongdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::clongdouble_tag>((npy_clongdouble *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::datetime_tag, npy_datetime>(npy_datetime *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_datetime(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::datetime_tag>((npy_datetime *)start, n);
 }
+
+template NPY_NO_EXPORT int
+heapsort_<npy::timedelta_tag, npy_timedelta>(npy_timedelta *, npy_intp);
 NPY_NO_EXPORT int
 heapsort_timedelta(void *start, npy_intp n, void *NPY_UNUSED(varr))
 {
     return heapsort_<npy::timedelta_tag>((npy_timedelta *)start, n);
 }
 
+template NPY_NO_EXPORT int
+aheapsort_<npy::bool_tag, npy_bool>(npy_bool *vv, npy_intp *tosort,
+                                    npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_bool(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::bool_tag>((npy_bool *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::byte_tag, npy_byte>(npy_byte *vv, npy_intp *tosort,
+                                    npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_byte(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::byte_tag>((npy_byte *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::ubyte_tag, npy_ubyte>(npy_ubyte *vv, npy_intp *tosort,
+                                      npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_ubyte(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::ubyte_tag>((npy_ubyte *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::short_tag, npy_short>(npy_short *vv, npy_intp *tosort,
+                                      npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_short(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::short_tag>((npy_short *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::ushort_tag, npy_ushort>(npy_ushort *vv, npy_intp *tosort,
+                                        npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_ushort(void *vv, npy_intp *tosort, npy_intp n,
                  void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::ushort_tag>((npy_ushort *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::int_tag, npy_int>(npy_int *vv, npy_intp *tosort, npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_int(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::int_tag>((npy_int *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::uint_tag, npy_uint>(npy_uint *vv, npy_intp *tosort,
+                                    npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_uint(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::uint_tag>((npy_uint *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::long_tag, npy_long>(npy_long *vv, npy_intp *tosort,
+                                    npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_long(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::long_tag>((npy_long *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::ulong_tag, npy_ulong>(npy_ulong *vv, npy_intp *tosort,
+                                      npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_ulong(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::ulong_tag>((npy_ulong *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::longlong_tag, npy_longlong>(npy_longlong *vv, npy_intp *tosort,
+                                            npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_longlong(void *vv, npy_intp *tosort, npy_intp n,
                    void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::longlong_tag>((npy_longlong *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::ulonglong_tag, npy_ulonglong>(npy_ulonglong *vv,
+                                              npy_intp *tosort, npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_ulonglong(void *vv, npy_intp *tosort, npy_intp n,
                     void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::ulonglong_tag>((npy_ulonglong *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::half_tag, npy_half>(npy_half *vv, npy_intp *tosort,
+                                    npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_half(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::half_tag>((npy_half *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::float_tag, npy_float>(npy_float *vv, npy_intp *tosort,
+                                      npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_float(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::float_tag>((npy_float *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::double_tag, npy_double>(npy_double *vv, npy_intp *tosort,
+                                        npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_double(void *vv, npy_intp *tosort, npy_intp n,
                  void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::double_tag>((npy_double *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::longdouble_tag, npy_longdouble>(npy_longdouble *vv,
+                                                npy_intp *tosort, npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_longdouble(void *vv, npy_intp *tosort, npy_intp n,
                      void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::longdouble_tag>((npy_longdouble *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::cfloat_tag, npy_cfloat>(npy_cfloat *vv, npy_intp *tosort,
+                                        npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_cfloat(void *vv, npy_intp *tosort, npy_intp n,
                  void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::cfloat_tag>((npy_cfloat *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::cdouble_tag, npy_cdouble>(npy_cdouble *vv, npy_intp *tosort,
+                                          npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_cdouble(void *vv, npy_intp *tosort, npy_intp n,
                   void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::cdouble_tag>((npy_cdouble *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::clongdouble_tag, npy_clongdouble>(npy_clongdouble *vv,
+                                                  npy_intp *tosort,
+                                                  npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_clongdouble(void *vv, npy_intp *tosort, npy_intp n,
                       void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::clongdouble_tag>((npy_clongdouble *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::datetime_tag, npy_datetime>(npy_datetime *vv, npy_intp *tosort,
+                                            npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_datetime(void *vv, npy_intp *tosort, npy_intp n,
                    void *NPY_UNUSED(varr))
 {
     return aheapsort_<npy::datetime_tag>((npy_datetime *)vv, tosort, n);
 }
+
+template NPY_NO_EXPORT int
+aheapsort_<npy::timedelta_tag, npy_timedelta>(npy_timedelta *vv,
+                                              npy_intp *tosort, npy_intp n);
 NPY_NO_EXPORT int
 aheapsort_timedelta(void *vv, npy_intp *tosort, npy_intp n,
                     void *NPY_UNUSED(varr))
diff --git a/numpy/core/src/npysort/quicksort.c.src b/numpy/core/src/npysort/quicksort.c.src
deleted file mode 100644
index b4b060720..000000000
--- a/numpy/core/src/npysort/quicksort.c.src
+++ /dev/null
@@ -1,651 +0,0 @@
-/* -*- c -*- */
-
-/*
- * The purpose of this module is to add faster sort functions
- * that are type-specific.  This is done by altering the
- * function table for the builtin descriptors.
- *
- * These sorting functions are copied almost directly from numarray
- * with a few modifications (complex comparisons compare the imaginary
- * part if the real parts are equal, for example), and the names
- * are changed.
- *
- * The original sorting code is due to Charles R. Harris who wrote
- * it for numarray.
- */
-
-/*
- * Quick sort is usually the fastest, but the worst case scenario is O(N^2) so
- * the code switches to the O(NlogN) worst case heapsort if not enough progress
- * is made on the large side of the two quicksort partitions. This improves the
- * worst case while still retaining the speed of quicksort for the common case.
- * This is variant known as introsort.
- *
- *
- * def introsort(lower, higher, recursion_limit=log2(higher - lower + 1) * 2):
- *   # sort remainder with heapsort if we are not making enough progress
- *   # we arbitrarily choose 2 * log(n) as the cutoff point
- *   if recursion_limit < 0:
- *       heapsort(lower, higher)
- *       return
- *
- *   if lower < higher:
- *      pivot_pos = partition(lower, higher)
- *      # recurse into smaller first and leave larger on stack
- *      # this limits the required stack space
- *      if (pivot_pos - lower > higher - pivot_pos):
- *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
- *          quicksort(lower, pivot_pos, recursion_limit - 1)
- *      else:
- *          quicksort(lower, pivot_pos, recursion_limit - 1)
- *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
- *
- *
- * the below code implements this converted to an iteration and as an
- * additional minor optimization skips the recursion depth checking on the
- * smaller partition as it is always less than half of the remaining data and
- * will thus terminate fast enough
- */
-
-#define NPY_NO_DEPRECATED_API NPY_API_VERSION
-
-#include "npy_sort.h"
-#include "npysort_common.h"
-#include "npy_cpu_features.h"
-#include "x86-qsort.h"
-#include <stdlib.h>
-
-#ifndef NPY_DISABLE_OPTIMIZATION
-    #include "x86-qsort.dispatch.h"
-#endif
-
-#define NOT_USED NPY_UNUSED(unused)
-/*
- * pushing largest partition has upper bound of log2(n) space
- * we store two pointers each time
- */
-#define PYA_QS_STACK (NPY_BITSOF_INTP * 2)
-#define SMALL_QUICKSORT 15
-#define SMALL_MERGESORT 20
-#define SMALL_STRING 16
-
-
-/*
- *****************************************************************************
- **                            NUMERIC SORTS                                **
- *****************************************************************************
- */
-
-
-/**begin repeat
- *
- * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
- *         LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE,
- *         CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
- * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
- *         longlong, ulonglong, half, float, double, longdouble,
- *         cfloat, cdouble, clongdouble, datetime, timedelta#
- * #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
- *         npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong,
- *         npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat,
- *         npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta#
- * #AVX512 = 0*5, 1, 1, 0*5, 1, 0*7#
- */
-
-NPY_NO_EXPORT int
-quicksort_@suff@(void *start, npy_intp num, void *NOT_USED)
-{
-
-#if @AVX512@
-    void (*dispfunc)(void*, npy_intp) = NULL;
-    NPY_CPU_DISPATCH_CALL_XB(dispfunc = &x86_quicksort_@suff@);
-    if (dispfunc) {
-       (*dispfunc)(start, num);
-       return 0;
-    }
-#endif
-
-    @type@ vp;
-    @type@ *pl = start;
-    @type@ *pr = pl + num - 1;
-    @type@ *stack[PYA_QS_STACK];
-    @type@ **sptr = stack;
-    @type@ *pm, *pi, *pj, *pk;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            heapsort_@suff@(pl, pr - pl + 1, NULL);
-            goto stack_pop;
-        }
-        while ((pr - pl) > SMALL_QUICKSORT) {
-            /* quicksort partition */
-            pm = pl + ((pr - pl) >> 1);
-            if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl);
-            if (@TYPE@_LT(*pr, *pm)) @TYPE@_SWAP(*pr, *pm);
-            if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl);
-            vp = *pm;
-            pi = pl;
-            pj = pr - 1;
-            @TYPE@_SWAP(*pm, *pj);
-            for (;;) {
-                do ++pi; while (@TYPE@_LT(*pi, vp));
-                do --pj; while (@TYPE@_LT(vp, *pj));
-                if (pi >= pj) {
-                    break;
-                }
-                @TYPE@_SWAP(*pi,*pj);
-            }
-            pk = pr - 1;
-            @TYPE@_SWAP(*pi, *pk);
-            /* push largest partition on stack */
-            if (pi - pl < pr - pi) {
-                *sptr++ = pi + 1;
-                *sptr++ = pr;
-                pr = pi - 1;
-            }
-            else {
-                *sptr++ = pl;
-                *sptr++ = pi - 1;
-                pl = pi + 1;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* insertion sort */
-        for (pi = pl + 1; pi <= pr; ++pi) {
-            vp = *pi;
-            pj = pi;
-            pk = pi - 1;
-            while (pj > pl && @TYPE@_LT(vp, *pk)) {
-                *pj-- = *pk--;
-            }
-            *pj = vp;
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    return 0;
-}
-
-
-NPY_NO_EXPORT int
-aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *NOT_USED)
-{
-    @type@ *v = vv;
-    @type@ vp;
-    npy_intp *pl = tosort;
-    npy_intp *pr = tosort + num - 1;
-    npy_intp *stack[PYA_QS_STACK];
-    npy_intp **sptr = stack;
-    npy_intp *pm, *pi, *pj, *pk, vi;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            aheapsort_@suff@(vv, pl, pr - pl + 1, NULL);
-            goto stack_pop;
-        }
-        while ((pr - pl) > SMALL_QUICKSORT) {
-            /* quicksort partition */
-            pm = pl + ((pr - pl) >> 1);
-            if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl);
-            if (@TYPE@_LT(v[*pr],v[*pm])) INTP_SWAP(*pr, *pm);
-            if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl);
-            vp = v[*pm];
-            pi = pl;
-            pj = pr - 1;
-            INTP_SWAP(*pm, *pj);
-            for (;;) {
-                do ++pi; while (@TYPE@_LT(v[*pi], vp));
-                do --pj; while (@TYPE@_LT(vp, v[*pj]));
-                if (pi >= pj) {
-                    break;
-                }
-                INTP_SWAP(*pi, *pj);
-            }
-            pk = pr - 1;
-            INTP_SWAP(*pi,*pk);
-            /* push largest partition on stack */
-            if (pi - pl < pr - pi) {
-                *sptr++ = pi + 1;
-                *sptr++ = pr;
-                pr = pi - 1;
-            }
-            else {
-                *sptr++ = pl;
-                *sptr++ = pi - 1;
-                pl = pi + 1;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* insertion sort */
-        for (pi = pl + 1; pi <= pr; ++pi) {
-            vi = *pi;
-            vp = v[vi];
-            pj = pi;
-            pk = pi - 1;
-            while (pj > pl && @TYPE@_LT(vp, v[*pk])) {
-                *pj-- = *pk--;
-            }
-            *pj = vi;
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    return 0;
-}
-
-/**end repeat**/
-
-
-/*
- *****************************************************************************
- **                             STRING SORTS                                **
- *****************************************************************************
- */
-
-
-/**begin repeat
- *
- * #TYPE = STRING, UNICODE#
- * #suff = string, unicode#
- * #type = npy_char, npy_ucs4#
- */
-
-NPY_NO_EXPORT int
-quicksort_@suff@(void *start, npy_intp num, void *varr)
-{
-    PyArrayObject *arr = varr;
-    const size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@);
-    @type@ *vp;
-    @type@ *pl = start;
-    @type@ *pr = pl + (num - 1)*len;
-    @type@ *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    /* Items that have zero size don't make sense to sort */
-    if (len == 0) {
-        return 0;
-    }
-
-    vp = malloc(PyArray_ITEMSIZE(arr));
-    if (vp == NULL) {
-        return -NPY_ENOMEM;
-    }
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            heapsort_@suff@(pl, (pr - pl) / len + 1, varr);
-            goto stack_pop;
-        }
-        while ((size_t)(pr - pl) > SMALL_QUICKSORT*len) {
-            /* quicksort partition */
-            pm = pl + (((pr - pl)/len) >> 1)*len;
-            if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len);
-            if (@TYPE@_LT(pr, pm, len)) @TYPE@_SWAP(pr, pm, len);
-            if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len);
-            @TYPE@_COPY(vp, pm, len);
-            pi = pl;
-            pj = pr - len;
-            @TYPE@_SWAP(pm, pj, len);
-            for (;;) {
-                do pi += len; while (@TYPE@_LT(pi, vp, len));
-                do pj -= len; while (@TYPE@_LT(vp, pj, len));
-                if (pi >= pj) {
-                    break;
-                }
-                @TYPE@_SWAP(pi, pj, len);
-            }
-            pk = pr - len;
-            @TYPE@_SWAP(pi, pk, len);
-            /* push largest partition on stack */
-            if (pi - pl < pr - pi) {
-                *sptr++ = pi + len;
-                *sptr++ = pr;
-                pr = pi - len;
-            }
-            else {
-                *sptr++ = pl;
-                *sptr++ = pi - len;
-                pl = pi + len;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* insertion sort */
-        for (pi = pl + len; pi <= pr; pi += len) {
-            @TYPE@_COPY(vp, pi, len);
-            pj = pi;
-            pk = pi - len;
-            while (pj > pl && @TYPE@_LT(vp, pk, len)) {
-                @TYPE@_COPY(pj, pk, len);
-                pj -= len;
-                pk -= len;
-            }
-            @TYPE@_COPY(pj, vp, len);
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    free(vp);
-    return 0;
-}
-
-
-NPY_NO_EXPORT int
-aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *varr)
-{
-    @type@ *v = vv;
-    PyArrayObject *arr = varr;
-    size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@);
-    @type@ *vp;
-    npy_intp *pl = tosort;
-    npy_intp *pr = tosort + num - 1;
-    npy_intp *stack[PYA_QS_STACK];
-    npy_intp **sptr=stack;
-    npy_intp *pm, *pi, *pj, *pk, vi;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    /* Items that have zero size don't make sense to sort */
-    if (len == 0) {
-        return 0;
-    }
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            aheapsort_@suff@(vv, pl, pr - pl + 1, varr);
-            goto stack_pop;
-        }
-        while ((pr - pl) > SMALL_QUICKSORT) {
-            /* quicksort partition */
-            pm = pl + ((pr - pl) >> 1);
-            if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl);
-            if (@TYPE@_LT(v + (*pr)*len, v + (*pm)*len, len)) INTP_SWAP(*pr, *pm);
-            if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl);
-            vp = v + (*pm)*len;
-            pi = pl;
-            pj = pr - 1;
-            INTP_SWAP(*pm,*pj);
-            for (;;) {
-                do ++pi; while (@TYPE@_LT(v + (*pi)*len, vp, len));
-                do --pj; while (@TYPE@_LT(vp, v + (*pj)*len, len));
-                if (pi >= pj) {
-                    break;
-                }
-                INTP_SWAP(*pi,*pj);
-            }
-            pk = pr - 1;
-            INTP_SWAP(*pi,*pk);
-            /* push largest partition on stack */
-            if (pi - pl < pr - pi) {
-                *sptr++ = pi + 1;
-                *sptr++ = pr;
-                pr = pi - 1;
-            }
-            else {
-                *sptr++ = pl;
-                *sptr++ = pi - 1;
-                pl = pi + 1;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* insertion sort */
-        for (pi = pl + 1; pi <= pr; ++pi) {
-            vi = *pi;
-            vp = v + vi*len;
-            pj = pi;
-            pk = pi - 1;
-            while (pj > pl && @TYPE@_LT(vp, v + (*pk)*len, len)) {
-                *pj-- = *pk--;
-            }
-            *pj = vi;
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    return 0;
-}
-
-/**end repeat**/
-
-
-/*
- *****************************************************************************
- **                             GENERIC SORT                                **
- *****************************************************************************
- */
-
-
-NPY_NO_EXPORT int
-npy_quicksort(void *start, npy_intp num, void *varr)
-{
-    PyArrayObject *arr = varr;
-    npy_intp elsize = PyArray_ITEMSIZE(arr);
-    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
-    char *vp;
-    char *pl = start;
-    char *pr = pl + (num - 1)*elsize;
-    char *stack[PYA_QS_STACK];
-    char **sptr = stack;
-    char *pm, *pi, *pj, *pk;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    /* Items that have zero size don't make sense to sort */
-    if (elsize == 0) {
-        return 0;
-    }
-
-    vp = malloc(elsize);
-    if (vp == NULL) {
-        return -NPY_ENOMEM;
-    }
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            npy_heapsort(pl, (pr - pl) / elsize + 1, varr);
-            goto stack_pop;
-        }
-        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);
-            /*
-             * Generic comparisons may be buggy, so don't rely on the sentinels
-             * to keep the pointers from going out of bounds.
-             */
-            for (;;) {
-                do {
-                    pi += elsize;
-                } while (cmp(pi, vp, arr) < 0 && pi < pj);
-                do {
-                    pj -= elsize;
-                } while (cmp(vp, pj, arr) < 0 && pi < pj);
-                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;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* 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);
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    free(vp);
-    return 0;
-}
-
-
-NPY_NO_EXPORT int
-npy_aquicksort(void *vv, npy_intp* tosort, npy_intp num, void *varr)
-{
-    char *v = vv;
-    PyArrayObject *arr = varr;
-    npy_intp elsize = PyArray_ITEMSIZE(arr);
-    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
-    char *vp;
-    npy_intp *pl = tosort;
-    npy_intp *pr = tosort + num - 1;
-    npy_intp *stack[PYA_QS_STACK];
-    npy_intp **sptr = stack;
-    npy_intp *pm, *pi, *pj, *pk, vi;
-    int depth[PYA_QS_STACK];
-    int * psdepth = depth;
-    int cdepth = npy_get_msb(num) * 2;
-
-    /* Items that have zero size don't make sense to sort */
-    if (elsize == 0) {
-        return 0;
-    }
-
-    for (;;) {
-        if (NPY_UNLIKELY(cdepth < 0)) {
-            npy_aheapsort(vv, pl, pr - pl + 1, varr);
-            goto stack_pop;
-        }
-        while ((pr - pl) > SMALL_QUICKSORT) {
-            /* quicksort partition */
-            pm = pl + ((pr - pl) >> 1);
-            if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) {
-                INTP_SWAP(*pm, *pl);
-            }
-            if (cmp(v + (*pr)*elsize, v + (*pm)*elsize, arr) < 0) {
-                INTP_SWAP(*pr, *pm);
-            }
-            if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) {
-                INTP_SWAP(*pm, *pl);
-            }
-            vp = v + (*pm)*elsize;
-            pi = pl;
-            pj = pr - 1;
-            INTP_SWAP(*pm,*pj);
-            for (;;) {
-                do {
-                    ++pi;
-                } while (cmp(v + (*pi)*elsize, vp, arr) < 0 && pi < pj);
-                do {
-                    --pj;
-                } while (cmp(vp, v + (*pj)*elsize, arr) < 0 && pi < pj);
-                if (pi >= pj) {
-                    break;
-                }
-                INTP_SWAP(*pi,*pj);
-            }
-            pk = pr - 1;
-            INTP_SWAP(*pi,*pk);
-            /* push largest partition on stack */
-            if (pi - pl < pr - pi) {
-                *sptr++ = pi + 1;
-                *sptr++ = pr;
-                pr = pi - 1;
-            }
-            else {
-                *sptr++ = pl;
-                *sptr++ = pi - 1;
-                pl = pi + 1;
-            }
-            *psdepth++ = --cdepth;
-        }
-
-        /* insertion sort */
-        for (pi = pl + 1; pi <= pr; ++pi) {
-            vi = *pi;
-            vp = v + vi*elsize;
-            pj = pi;
-            pk = pi - 1;
-            while (pj > pl && cmp(vp, v + (*pk)*elsize, arr) < 0) {
-                *pj-- = *pk--;
-            }
-            *pj = vi;
-        }
-stack_pop:
-        if (sptr == stack) {
-            break;
-        }
-        pr = *(--sptr);
-        pl = *(--sptr);
-        cdepth = *(--psdepth);
-    }
-
-    return 0;
-}
diff --git a/numpy/core/src/npysort/quicksort.cpp b/numpy/core/src/npysort/quicksort.cpp
new file mode 100644
index 000000000..c6b87524d
--- /dev/null
+++ b/numpy/core/src/npysort/quicksort.cpp
@@ -0,0 +1,944 @@
+/* -*- c -*- */
+
+/*
+ * The purpose of this module is to add faster sort functions
+ * that are type-specific.  This is done by altering the
+ * function table for the builtin descriptors.
+ *
+ * These sorting functions are copied almost directly from numarray
+ * with a few modifications (complex comparisons compare the imaginary
+ * part if the real parts are equal, for example), and the names
+ * are changed.
+ *
+ * The original sorting code is due to Charles R. Harris who wrote
+ * it for numarray.
+ */
+
+/*
+ * Quick sort is usually the fastest, but the worst case scenario is O(N^2) so
+ * the code switches to the O(NlogN) worst case heapsort if not enough progress
+ * is made on the large side of the two quicksort partitions. This improves the
+ * worst case while still retaining the speed of quicksort for the common case.
+ * This is variant known as introsort.
+ *
+ *
+ * def introsort(lower, higher, recursion_limit=log2(higher - lower + 1) * 2):
+ *   # sort remainder with heapsort if we are not making enough progress
+ *   # we arbitrarily choose 2 * log(n) as the cutoff point
+ *   if recursion_limit < 0:
+ *       heapsort(lower, higher)
+ *       return
+ *
+ *   if lower < higher:
+ *      pivot_pos = partition(lower, higher)
+ *      # recurse into smaller first and leave larger on stack
+ *      # this limits the required stack space
+ *      if (pivot_pos - lower > higher - pivot_pos):
+ *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
+ *          quicksort(lower, pivot_pos, recursion_limit - 1)
+ *      else:
+ *          quicksort(lower, pivot_pos, recursion_limit - 1)
+ *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
+ *
+ *
+ * the below code implements this converted to an iteration and as an
+ * additional minor optimization skips the recursion depth checking on the
+ * smaller partition as it is always less than half of the remaining data and
+ * will thus terminate fast enough
+ */
+
+#define NPY_NO_DEPRECATED_API NPY_API_VERSION
+
+#include "npy_cpu_features.h"
+#include "npy_sort.h"
+#include "npysort_common.h"
+#include "numpy_tag.h"
+
+#include "x86-qsort.h"
+#include <cstdlib>
+#include <utility>
+
+#ifndef NPY_DISABLE_OPTIMIZATION
+#include "x86-qsort.dispatch.h"
+#endif
+
+#define NOT_USED NPY_UNUSED(unused)
+/*
+ * pushing largest partition has upper bound of log2(n) space
+ * we store two pointers each time
+ */
+#define PYA_QS_STACK (NPY_BITSOF_INTP * 2)
+#define SMALL_QUICKSORT 15
+#define SMALL_MERGESORT 20
+#define SMALL_STRING 16
+
+/*
+ *****************************************************************************
+ **                            NUMERIC SORTS                                **
+ *****************************************************************************
+ */
+
+template <typename Tag, typename type>
+NPY_NO_EXPORT int
+heapsort_(type *start, npy_intp n);
+template <typename Tag, typename type>
+NPY_NO_EXPORT int
+aheapsort_(type *vv, npy_intp *tosort, npy_intp n);
+template <typename Tag, typename type>
+NPY_NO_EXPORT int
+string_heapsort_(type *start, npy_intp n, void *varr);
+template <typename Tag, typename type>
+NPY_NO_EXPORT int
+string_aheapsort_(type *vv, npy_intp *tosort, npy_intp n, void *varr);
+
+namespace {
+
+template <typename Tag>
+struct x86_dispatch {
+    static bool quicksort(typename Tag::type *, npy_intp) { return false; }
+};
+
+template <>
+struct x86_dispatch<npy::int_tag> {
+    static bool quicksort(npy_int *start, npy_intp num)
+    {
+        void (*dispfunc)(void *, npy_intp) = nullptr;
+        NPY_CPU_DISPATCH_CALL_XB(dispfunc = x86_quicksort_int);
+        if (dispfunc) {
+            (*dispfunc)(start, num);
+            return true;
+        }
+        return false;
+    }
+};
+
+template <>
+struct x86_dispatch<npy::uint_tag> {
+    static bool quicksort(npy_uint *start, npy_intp num)
+    {
+        void (*dispfunc)(void *, npy_intp) = nullptr;
+        NPY_CPU_DISPATCH_CALL_XB(dispfunc = x86_quicksort_uint);
+        if (dispfunc) {
+            (*dispfunc)(start, num);
+            return true;
+        }
+        return false;
+    }
+};
+
+template <>
+struct x86_dispatch<npy::float_tag> {
+    static bool quicksort(npy_float *start, npy_intp num)
+    {
+        void (*dispfunc)(void *, npy_intp) = nullptr;
+        NPY_CPU_DISPATCH_CALL_XB(dispfunc = x86_quicksort_float);
+        if (dispfunc) {
+            (*dispfunc)(start, num);
+            return true;
+        }
+        return false;
+    }
+};
+
+}  // namespace
+
+template <typename Tag, typename type>
+static int
+quicksort_(type *start, npy_intp num)
+{
+    if (x86_dispatch<Tag>::quicksort(start, num))
+        return 0;
+
+    type vp;
+    type *pl = start;
+    type *pr = pl + num - 1;
+    type *stack[PYA_QS_STACK];
+    type **sptr = stack;
+    type *pm, *pi, *pj, *pk;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            heapsort_<Tag>(pl, pr - pl + 1);
+            goto stack_pop;
+        }
+        while ((pr - pl) > SMALL_QUICKSORT) {
+            /* quicksort partition */
+            pm = pl + ((pr - pl) >> 1);
+            if (Tag::less(*pm, *pl))
+                std::swap(*pm, *pl);
+            if (Tag::less(*pr, *pm))
+                std::swap(*pr, *pm);
+            if (Tag::less(*pm, *pl))
+                std::swap(*pm, *pl);
+            vp = *pm;
+            pi = pl;
+            pj = pr - 1;
+            std::swap(*pm, *pj);
+            for (;;) {
+                do ++pi;
+                while (Tag::less(*pi, vp));
+                do --pj;
+                while (Tag::less(vp, *pj));
+                if (pi >= pj) {
+                    break;
+                }
+                std::swap(*pi, *pj);
+            }
+            pk = pr - 1;
+            std::swap(*pi, *pk);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + 1;
+                *sptr++ = pr;
+                pr = pi - 1;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - 1;
+                pl = pi + 1;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* insertion sort */
+        for (pi = pl + 1; pi <= pr; ++pi) {
+            vp = *pi;
+            pj = pi;
+            pk = pi - 1;
+            while (pj > pl && Tag::less(vp, *pk)) {
+                *pj-- = *pk--;
+            }
+            *pj = vp;
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    return 0;
+}
+
+template <typename Tag, typename type>
+static int
+aquicksort_(type *vv, npy_intp *tosort, npy_intp num)
+{
+    type *v = vv;
+    type vp;
+    npy_intp *pl = tosort;
+    npy_intp *pr = tosort + num - 1;
+    npy_intp *stack[PYA_QS_STACK];
+    npy_intp **sptr = stack;
+    npy_intp *pm, *pi, *pj, *pk, vi;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            aheapsort_<Tag>(vv, pl, pr - pl + 1);
+            goto stack_pop;
+        }
+        while ((pr - pl) > SMALL_QUICKSORT) {
+            /* quicksort partition */
+            pm = pl + ((pr - pl) >> 1);
+            if (Tag::less(v[*pm], v[*pl]))
+                std::swap(*pm, *pl);
+            if (Tag::less(v[*pr], v[*pm]))
+                std::swap(*pr, *pm);
+            if (Tag::less(v[*pm], v[*pl]))
+                std::swap(*pm, *pl);
+            vp = v[*pm];
+            pi = pl;
+            pj = pr - 1;
+            std::swap(*pm, *pj);
+            for (;;) {
+                do ++pi;
+                while (Tag::less(v[*pi], vp));
+                do --pj;
+                while (Tag::less(vp, v[*pj]));
+                if (pi >= pj) {
+                    break;
+                }
+                std::swap(*pi, *pj);
+            }
+            pk = pr - 1;
+            std::swap(*pi, *pk);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + 1;
+                *sptr++ = pr;
+                pr = pi - 1;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - 1;
+                pl = pi + 1;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* insertion sort */
+        for (pi = pl + 1; pi <= pr; ++pi) {
+            vi = *pi;
+            vp = v[vi];
+            pj = pi;
+            pk = pi - 1;
+            while (pj > pl && Tag::less(vp, v[*pk])) {
+                *pj-- = *pk--;
+            }
+            *pj = vi;
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    return 0;
+}
+
+/*
+ *****************************************************************************
+ **                             STRING SORTS                                **
+ *****************************************************************************
+ */
+
+template <typename Tag, typename type>
+static int
+string_quicksort_(type *start, npy_intp num, void *varr)
+{
+    PyArrayObject *arr = (PyArrayObject *)varr;
+    const size_t len = PyArray_ITEMSIZE(arr) / sizeof(type);
+    type *vp;
+    type *pl = start;
+    type *pr = pl + (num - 1) * len;
+    type *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    /* Items that have zero size don't make sense to sort */
+    if (len == 0) {
+        return 0;
+    }
+
+    vp = (type *)malloc(PyArray_ITEMSIZE(arr));
+    if (vp == NULL) {
+        return -NPY_ENOMEM;
+    }
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            string_heapsort_<Tag>(pl, (pr - pl) / len + 1, varr);
+            goto stack_pop;
+        }
+        while ((size_t)(pr - pl) > SMALL_QUICKSORT * len) {
+            /* quicksort partition */
+            pm = pl + (((pr - pl) / len) >> 1) * len;
+            if (Tag::less(pm, pl, len))
+                Tag::swap(pm, pl, len);
+            if (Tag::less(pr, pm, len))
+                Tag::swap(pr, pm, len);
+            if (Tag::less(pm, pl, len))
+                Tag::swap(pm, pl, len);
+            Tag::copy(vp, pm, len);
+            pi = pl;
+            pj = pr - len;
+            Tag::swap(pm, pj, len);
+            for (;;) {
+                do pi += len;
+                while (Tag::less(pi, vp, len));
+                do pj -= len;
+                while (Tag::less(vp, pj, len));
+                if (pi >= pj) {
+                    break;
+                }
+                Tag::swap(pi, pj, len);
+            }
+            pk = pr - len;
+            Tag::swap(pi, pk, len);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + len;
+                *sptr++ = pr;
+                pr = pi - len;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - len;
+                pl = pi + len;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* insertion sort */
+        for (pi = pl + len; pi <= pr; pi += len) {
+            Tag::copy(vp, pi, len);
+            pj = pi;
+            pk = pi - len;
+            while (pj > pl && Tag::less(vp, pk, len)) {
+                Tag::copy(pj, pk, len);
+                pj -= len;
+                pk -= len;
+            }
+            Tag::copy(pj, vp, len);
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    free(vp);
+    return 0;
+}
+
+template <typename Tag, typename type>
+static int
+string_aquicksort_(type *vv, npy_intp *tosort, npy_intp num, void *varr)
+{
+    type *v = vv;
+    PyArrayObject *arr = (PyArrayObject *)varr;
+    size_t len = PyArray_ITEMSIZE(arr) / sizeof(type);
+    type *vp;
+    npy_intp *pl = tosort;
+    npy_intp *pr = tosort + num - 1;
+    npy_intp *stack[PYA_QS_STACK];
+    npy_intp **sptr = stack;
+    npy_intp *pm, *pi, *pj, *pk, vi;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    /* Items that have zero size don't make sense to sort */
+    if (len == 0) {
+        return 0;
+    }
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            string_aheapsort_<Tag>(vv, pl, pr - pl + 1, varr);
+            goto stack_pop;
+        }
+        while ((pr - pl) > SMALL_QUICKSORT) {
+            /* quicksort partition */
+            pm = pl + ((pr - pl) >> 1);
+            if (Tag::less(v + (*pm) * len, v + (*pl) * len, len))
+                std::swap(*pm, *pl);
+            if (Tag::less(v + (*pr) * len, v + (*pm) * len, len))
+                std::swap(*pr, *pm);
+            if (Tag::less(v + (*pm) * len, v + (*pl) * len, len))
+                std::swap(*pm, *pl);
+            vp = v + (*pm) * len;
+            pi = pl;
+            pj = pr - 1;
+            std::swap(*pm, *pj);
+            for (;;) {
+                do ++pi;
+                while (Tag::less(v + (*pi) * len, vp, len));
+                do --pj;
+                while (Tag::less(vp, v + (*pj) * len, len));
+                if (pi >= pj) {
+                    break;
+                }
+                std::swap(*pi, *pj);
+            }
+            pk = pr - 1;
+            std::swap(*pi, *pk);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + 1;
+                *sptr++ = pr;
+                pr = pi - 1;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - 1;
+                pl = pi + 1;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* insertion sort */
+        for (pi = pl + 1; pi <= pr; ++pi) {
+            vi = *pi;
+            vp = v + vi * len;
+            pj = pi;
+            pk = pi - 1;
+            while (pj > pl && Tag::less(vp, v + (*pk) * len, len)) {
+                *pj-- = *pk--;
+            }
+            *pj = vi;
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    return 0;
+}
+
+/*
+ *****************************************************************************
+ **                             GENERIC SORT                                **
+ *****************************************************************************
+ */
+
+NPY_NO_EXPORT int
+npy_quicksort(void *start, npy_intp num, void *varr)
+{
+    PyArrayObject *arr = (PyArrayObject *)varr;
+    npy_intp elsize = PyArray_ITEMSIZE(arr);
+    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
+    char *vp;
+    char *pl = (char *)start;
+    char *pr = pl + (num - 1) * elsize;
+    char *stack[PYA_QS_STACK];
+    char **sptr = stack;
+    char *pm, *pi, *pj, *pk;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    /* Items that have zero size don't make sense to sort */
+    if (elsize == 0) {
+        return 0;
+    }
+
+    vp = (char *)malloc(elsize);
+    if (vp == NULL) {
+        return -NPY_ENOMEM;
+    }
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            npy_heapsort(pl, (pr - pl) / elsize + 1, varr);
+            goto stack_pop;
+        }
+        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);
+            /*
+             * Generic comparisons may be buggy, so don't rely on the sentinels
+             * to keep the pointers from going out of bounds.
+             */
+            for (;;) {
+                do {
+                    pi += elsize;
+                } while (cmp(pi, vp, arr) < 0 && pi < pj);
+                do {
+                    pj -= elsize;
+                } while (cmp(vp, pj, arr) < 0 && pi < pj);
+                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;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* 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);
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    free(vp);
+    return 0;
+}
+
+NPY_NO_EXPORT int
+npy_aquicksort(void *vv, npy_intp *tosort, npy_intp num, void *varr)
+{
+    char *v = (char *)vv;
+    PyArrayObject *arr = (PyArrayObject *)varr;
+    npy_intp elsize = PyArray_ITEMSIZE(arr);
+    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
+    char *vp;
+    npy_intp *pl = tosort;
+    npy_intp *pr = tosort + num - 1;
+    npy_intp *stack[PYA_QS_STACK];
+    npy_intp **sptr = stack;
+    npy_intp *pm, *pi, *pj, *pk, vi;
+    int depth[PYA_QS_STACK];
+    int *psdepth = depth;
+    int cdepth = npy_get_msb(num) * 2;
+
+    /* Items that have zero size don't make sense to sort */
+    if (elsize == 0) {
+        return 0;
+    }
+
+    for (;;) {
+        if (NPY_UNLIKELY(cdepth < 0)) {
+            npy_aheapsort(vv, pl, pr - pl + 1, varr);
+            goto stack_pop;
+        }
+        while ((pr - pl) > SMALL_QUICKSORT) {
+            /* quicksort partition */
+            pm = pl + ((pr - pl) >> 1);
+            if (cmp(v + (*pm) * elsize, v + (*pl) * elsize, arr) < 0) {
+                INTP_SWAP(*pm, *pl);
+            }
+            if (cmp(v + (*pr) * elsize, v + (*pm) * elsize, arr) < 0) {
+                INTP_SWAP(*pr, *pm);
+            }
+            if (cmp(v + (*pm) * elsize, v + (*pl) * elsize, arr) < 0) {
+                INTP_SWAP(*pm, *pl);
+            }
+            vp = v + (*pm) * elsize;
+            pi = pl;
+            pj = pr - 1;
+            INTP_SWAP(*pm, *pj);
+            for (;;) {
+                do {
+                    ++pi;
+                } while (cmp(v + (*pi) * elsize, vp, arr) < 0 && pi < pj);
+                do {
+                    --pj;
+                } while (cmp(vp, v + (*pj) * elsize, arr) < 0 && pi < pj);
+                if (pi >= pj) {
+                    break;
+                }
+                INTP_SWAP(*pi, *pj);
+            }
+            pk = pr - 1;
+            INTP_SWAP(*pi, *pk);
+            /* push largest partition on stack */
+            if (pi - pl < pr - pi) {
+                *sptr++ = pi + 1;
+                *sptr++ = pr;
+                pr = pi - 1;
+            }
+            else {
+                *sptr++ = pl;
+                *sptr++ = pi - 1;
+                pl = pi + 1;
+            }
+            *psdepth++ = --cdepth;
+        }
+
+        /* insertion sort */
+        for (pi = pl + 1; pi <= pr; ++pi) {
+            vi = *pi;
+            vp = v + vi * elsize;
+            pj = pi;
+            pk = pi - 1;
+            while (pj > pl && cmp(vp, v + (*pk) * elsize, arr) < 0) {
+                *pj-- = *pk--;
+            }
+            *pj = vi;
+        }
+    stack_pop:
+        if (sptr == stack) {
+            break;
+        }
+        pr = *(--sptr);
+        pl = *(--sptr);
+        cdepth = *(--psdepth);
+    }
+
+    return 0;
+}
+
+/***************************************
+ * C > C++ dispatch
+ ***************************************/
+
+NPY_NO_EXPORT int
+quicksort_bool(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::bool_tag>((npy_bool *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_byte(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::byte_tag>((npy_byte *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_ubyte(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::ubyte_tag>((npy_ubyte *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_short(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::short_tag>((npy_short *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_ushort(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::ushort_tag>((npy_ushort *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_int(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::int_tag>((npy_int *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_uint(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::uint_tag>((npy_uint *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_long(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::long_tag>((npy_long *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_ulong(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::ulong_tag>((npy_ulong *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_longlong(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::longlong_tag>((npy_longlong *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_ulonglong(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::ulonglong_tag>((npy_ulonglong *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_half(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::half_tag>((npy_half *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_float(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::float_tag>((npy_float *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_double(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::double_tag>((npy_double *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_longdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::longdouble_tag>((npy_longdouble *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_cfloat(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::cfloat_tag>((npy_cfloat *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_cdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::cdouble_tag>((npy_cdouble *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_clongdouble(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::clongdouble_tag>((npy_clongdouble *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_datetime(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::datetime_tag>((npy_datetime *)start, n);
+}
+NPY_NO_EXPORT int
+quicksort_timedelta(void *start, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return quicksort_<npy::timedelta_tag>((npy_timedelta *)start, n);
+}
+
+NPY_NO_EXPORT int
+aquicksort_bool(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::bool_tag>((npy_bool *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_byte(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::byte_tag>((npy_byte *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_ubyte(void *vv, npy_intp *tosort, npy_intp n,
+                 void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::ubyte_tag>((npy_ubyte *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_short(void *vv, npy_intp *tosort, npy_intp n,
+                 void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::short_tag>((npy_short *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_ushort(void *vv, npy_intp *tosort, npy_intp n,
+                  void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::ushort_tag>((npy_ushort *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_int(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::int_tag>((npy_int *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_uint(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::uint_tag>((npy_uint *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_long(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::long_tag>((npy_long *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_ulong(void *vv, npy_intp *tosort, npy_intp n,
+                 void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::ulong_tag>((npy_ulong *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_longlong(void *vv, npy_intp *tosort, npy_intp n,
+                    void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::longlong_tag>((npy_longlong *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_ulonglong(void *vv, npy_intp *tosort, npy_intp n,
+                     void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::ulonglong_tag>((npy_ulonglong *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_half(void *vv, npy_intp *tosort, npy_intp n, void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::half_tag>((npy_half *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_float(void *vv, npy_intp *tosort, npy_intp n,
+                 void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::float_tag>((npy_float *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_double(void *vv, npy_intp *tosort, npy_intp n,
+                  void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::double_tag>((npy_double *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_longdouble(void *vv, npy_intp *tosort, npy_intp n,
+                      void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::longdouble_tag>((npy_longdouble *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_cfloat(void *vv, npy_intp *tosort, npy_intp n,
+                  void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::cfloat_tag>((npy_cfloat *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_cdouble(void *vv, npy_intp *tosort, npy_intp n,
+                   void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::cdouble_tag>((npy_cdouble *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_clongdouble(void *vv, npy_intp *tosort, npy_intp n,
+                       void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::clongdouble_tag>((npy_clongdouble *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_datetime(void *vv, npy_intp *tosort, npy_intp n,
+                    void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::datetime_tag>((npy_datetime *)vv, tosort, n);
+}
+NPY_NO_EXPORT int
+aquicksort_timedelta(void *vv, npy_intp *tosort, npy_intp n,
+                     void *NPY_UNUSED(varr))
+{
+    return aquicksort_<npy::timedelta_tag>((npy_timedelta *)vv, tosort, n);
+}
+
+NPY_NO_EXPORT int
+quicksort_string(void *start, npy_intp n, void *varr)
+{
+    return string_quicksort_<npy::string_tag>((npy_char *)start, n, varr);
+}
+NPY_NO_EXPORT int
+quicksort_unicode(void *start, npy_intp n, void *varr)
+{
+    return string_quicksort_<npy::unicode_tag>((npy_ucs4 *)start, n, varr);
+}
+
+NPY_NO_EXPORT int
+aquicksort_string(void *vv, npy_intp *tosort, npy_intp n, void *varr)
+{
+    return string_aquicksort_<npy::string_tag>((npy_char *)vv, tosort, n,
+                                               varr);
+}
+NPY_NO_EXPORT int
+aquicksort_unicode(void *vv, npy_intp *tosort, npy_intp n, void *varr)
+{
+    return string_aquicksort_<npy::unicode_tag>((npy_ucs4 *)vv, tosort, n,
+                                                varr);
+}
diff --git a/numpy/core/src/npysort/x86-qsort.h b/numpy/core/src/npysort/x86-qsort.h
index 8cb8e3654..6340e2bc7 100644
--- a/numpy/core/src/npysort/x86-qsort.h
+++ b/numpy/core/src/npysort/x86-qsort.h
@@ -1,18 +1,28 @@
 #include "numpy/npy_common.h"
+
 #include "npy_cpu_dispatch.h"
 
 #ifndef NPY_NO_EXPORT
-    #define NPY_NO_EXPORT NPY_VISIBILITY_HIDDEN
+#define NPY_NO_EXPORT NPY_VISIBILITY_HIDDEN
 #endif
 
 #ifndef NPY_DISABLE_OPTIMIZATION
-    #include "x86-qsort.dispatch.h"
+#include "x86-qsort.dispatch.h"
+#endif
+
+#ifdef __cplusplus
+extern "C" {
 #endif
+
 NPY_CPU_DISPATCH_DECLARE(NPY_NO_EXPORT void x86_quicksort_int,
-             (void *start, npy_intp num))
+                         (void *start, npy_intp num))
 
 NPY_CPU_DISPATCH_DECLARE(NPY_NO_EXPORT void x86_quicksort_uint,
-             (void *start, npy_intp num))
+                         (void *start, npy_intp num))
 
 NPY_CPU_DISPATCH_DECLARE(NPY_NO_EXPORT void x86_quicksort_float,
-             (void *start, npy_intp num))
+                         (void *start, npy_intp num))
+
+#ifdef __cplusplus
+}
+#endif