numpy 2.0.0
src/npysort/sort.c.src File Reference
#include <stdlib.h>
#include "npy_sort.h"
#include "npysort_common.h"

Defines

#define NPY_NO_DEPRECATED_API
#define NOT_USED   NPY_UNUSED(unused)
#define PYA_QS_STACK   100
#define SMALL_QUICKSORT   15
#define SMALL_MERGESORT   20
#define SMALL_STRING   16

Functions

int quicksort_ suff (@type @*start, npy_intp num, void *NOT_USED)
int aquicksort_ suff (@type @*v, npy_intp *tosort, npy_intp num, void *NOT_USED)
static void mergesort0_ suff (@type @*pl,@type @*pr,@type @*pw)
static void amergesort0_ suff (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw)
static void mergesort0_ suff (@type @*pl,@type @*pr,@type @*pw,@type @*vp, size_t len)
int mergesort_ suff (@type @*start, npy_intp num, PyArrayObject *arr)
int aheapsort_ suff (@type @*v, npy_intp *tosort, npy_intp n, PyArrayObject *arr)
static void amergesort0_ suff (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw, int len)

Define Documentation

#define NOT_USED   NPY_UNUSED(unused)
#define NPY_NO_DEPRECATED_API
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 can be slower than the merge and heap sorts. The merge sort requires extra memory and so for large arrays may not be useful.
The merge sort is stable, meaning that equal components are unmoved from their entry versions, so it can be used to implement lexigraphic sorting on multiple keys.
The heap sort is included for completeness.
#define PYA_QS_STACK   100
#define SMALL_MERGESORT   20
#define SMALL_QUICKSORT   15

Referenced by suff().

#define SMALL_STRING   16

Function Documentation

int mergesort_ suff ( @type @*  start,
npy_intp  num,
void *  NOT_USED 
)

* NUMERIC SORTS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE#
suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong, half, float, double, longdouble, cfloat, cdouble, clongdouble#
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#

</blockquote>

quicksort partition
push largest partition on stack
insertion sort
The array needs to be offset by one for heapsort indexing

References SMALL_QUICKSORT, and TYPE.

static void amergesort0_ suff ( npy_intp pl,
npy_intp pr,
@type @*  v,
npy_intp pw,
int  len 
) [static]

merge sort
insertion sort

int amergesort_ suff ( @type @*  v,
npy_intp tosort,
npy_intp  n,
PyArrayObject arr 
)

The array needs to be offset by one for heapsort indexing
quicksort partition
push largest partition on stack
insertion sort

References INTP_SWAP, SMALL_QUICKSORT, and TYPE.

int heapsort_ suff ( @type @*  start,
npy_intp  num,
PyArrayObject arr 
)

quicksort partition
push largest partition on stack
insertion sort

static void mergesort0_ suff ( @type @*  pl,
@type @*  pr,
@type @*  pw,
@type @*  vp,
size_t  len 
) [static]
end repeat*

* STRING SORTS **

begin repeat <blockquote> TYPE = STRING, UNICODE# suff = string, unicode# type = npy_char, npy_ucs4#</blockquote>

merge sort
insertion sort

References PyDataMem_FREE, PyDataMem_NEW, suff(), and type().

static void amergesort0_ suff ( npy_intp pl,
npy_intp pr,
@type @*  v,
npy_intp pw 
) [static]

merge sort
insertion sort

static void mergesort0_ suff ( @type @*  pl,
@type @*  pr,
@type @*  pw 
) [static]

merge sort
insertion sort

int amergesort_ suff ( @type @*  v,
npy_intp tosort,
npy_intp  num,
void *  NOT_USED 
)

quicksort partition
push largest partition on stack
insertion sort
The arrays need to be offset by one for heapsort indexing