src/npysort/mergesort.c.src File Reference

#include "npy_sort.h"
#include "npysort_common.h"
#include <stdlib.h>

Defines
#define	NPY_NO_DEPRECATED_API   NPY_API_VERSION
#define	NOT_USED   NPY_UNUSED(unused)
#define	PYA_QS_STACK   100
#define	SMALL_QUICKSORT   15
#define	SMALL_MERGESORT   20
#define	SMALL_STRING   16
Functions
static void mergesort0_	suff (@type @*pl,@type @*pr,@type @*pw)
int mergesort_	suff (void *start, npy_intp num, void *NOT_USED)
static void amergesort0_	suff (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw)
int amergesort_	suff (void *v, npy_intp *tosort, npy_intp num, void *NOT_USED)
static void mergesort0_	suff (@type @*pl,@type @*pr,@type @*pw,@type @*vp, size_t len)
static void amergesort0_	suff (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw, size_t len)
static void	npy_mergesort0 (char *pl, char *pr, char *pw, char *vp, npy_intp elsize, PyArray_CompareFunc *cmp, PyArrayObject *arr)
int	npy_mergesort (void *start, npy_intp num, void *varr)
static void	npy_amergesort0 (npy_intp *pl, npy_intp *pr, char *v, npy_intp *pw, npy_intp elsize, PyArray_CompareFunc *cmp, PyArrayObject *arr)
int	npy_amergesort (void *v, npy_intp *tosort, npy_intp num, void *varr)

---

Define Documentation

#define NOT_USED   NPY_UNUSED(unused)

#define NPY_NO_DEPRECATED_API   NPY_API_VERSION

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

#define SMALL_STRING   16

---

Function Documentation

int npy_amergesort	(	void *	v,
		npy_intp *	tosort,
		npy_intp	num,
		void *	varr
	)

static void npy_amergesort0	(	npy_intp *	pl,
		npy_intp *	pr,
		char *	v,
		npy_intp *	pw,
		npy_intp	elsize,
		PyArray_CompareFunc *	cmp,
		PyArrayObject *	arr
	)		[static]

merge sort

insertion sort

int npy_mergesort	(	void *	start,
		npy_intp	num,
		void *	varr
	)

static void npy_mergesort0	(	char *	pl,
		char *	pr,
		char *	pw,
		char *	vp,
		npy_intp	elsize,
		PyArray_CompareFunc *	cmp,
		PyArrayObject *	arr
	)		[static]

end repeat*

* GENERIC SORT **

merge sort

insertion sort

References GENERIC_COPY().

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

* NUMERIC SORTS **

begin repeat <blockquote>

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#

</blockquote>

merge sort

insertion sort

References suff(), and TYPE.

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

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

merge sort

insertion sort

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

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

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

merge sort

insertion sort