Added other sort methods (heap, merge)

7 files changed, 345 insertions, 50 deletions

diff --git a/scipy/base/code_generators/multiarray_api_order.txt b/scipy/base/code_generators/multiarray_api_order.txt
index e1395c8aa..eacbfcd09 100644
--- a/scipy/base/code_generators/multiarray_api_order.txt
+++ b/scipy/base/code_generators/multiarray_api_order.txt
@@ -62,3 +62,4 @@ PyArray_Empty
 PyArray_Where
 PyArray_Arange
 PyArray_ArangeObj
+PyArray_SortkindConverter
diff --git a/scipy/base/include/scipy/arrayobject.h b/scipy/base/include/scipy/arrayobject.h
index b6f3e330d..bc9f685fc 100644
--- a/scipy/base/include/scipy/arrayobject.h
+++ b/scipy/base/include/scipy/arrayobject.h
@@ -212,7 +212,7 @@ typedef enum {
 	PyArray_QUICKSORT=0,
 	PyArray_HEAPSORT=1,
 	PyArray_MERGESORT=2,
-	PyArray_TIMSORT=3,
+	PyArray_TIMSORT=3,    /* the sort Python uses -- specialized */
 } PyArray_SORTKIND;
 #define PyArray_NSORTS PyArray_TIMSORT + 1
 
@@ -780,8 +780,8 @@ typedef int (PyArray_ScanFunc)(FILE *, void *, void *, void *);
 
 typedef int (PyArray_FillFunc)(void *, intp, void *);
 
-typedef void (PyArray_SortFunc)(void *, intp, int, void *);
-typedef void (PyArray_ArgSortFunc)(void *, intp *, intp, int, void *);
+typedef int (PyArray_SortFunc)(void *, intp, void *);
+typedef int (PyArray_ArgSortFunc)(void *, intp *, intp, void *);
 
 typedef struct {
         intp *ptr;
diff --git a/scipy/base/ma.py b/scipy/base/ma.py
index e0c81d8c8..3b8de05a3 100644
--- a/scipy/base/ma.py
+++ b/scipy/base/ma.py
@@ -610,7 +610,7 @@ class MaskedArray (object):
     def __array__ (self, t = None):
         "Special hook for numeric. Converts to numeric if possible."
         if self._mask is not None:
-            if oldnumeric.sometrue(oldnumeric.ravel(self._mask)):
+            if oldnumeric.ravel(self._mask).any():
                 raise MAError, \
                 """Cannot automatically convert masked array to numeric because data
                    is masked in one or more locations.
diff --git a/scipy/base/src/_sortmodule.c.src b/scipy/base/src/_sortmodule.c.src
index 2daad3663..96ed2fb98 100644
--- a/scipy/base/src/_sortmodule.c.src
+++ b/scipy/base/src/_sortmodule.c.src
@@ -20,10 +20,11 @@
 /**begin repeat
 #TYPE=BOOL,BYTE,UBYTE,SHORT,USHORT,INT,UINT,LONG,ULONG,LONGLONG,ULONGLONG,FLOAT,DOUBLE,LONGDOUBLE,CFLOAT,CDOUBLE,CLONGDOUBLE#
 #type=Bool,byte,ubyte,short,ushort,int,uint,long,ulong,longlong,ulonglong,float,double,longdouble,cfloat,cdouble,clongdouble#
-#comp=STDC_LT*14,NUMC_LT*3#
+#lessthan=STDC_LT*14,NUMC_LT*3#
+#lessequal=STDC_LE*14,NUMC_LE*3#
  **/
-static void 
-@TYPE@_quicksort(@type@ *start, intp num, int elsize, void *unused)
+static int
+@TYPE@_quicksort(@type@ *start, intp num, void *unused)
 {
 	@type@ *pl = start;
 	@type@ *pr = start + num - 1;
@@ -34,16 +35,16 @@ static void
                 while ((pr - pl) > 15) {
                         /* quicksort partition */
                         pm = pl + ((pr - pl) >> 1);
-                        if (@comp@(*pm,*pl)) SWAP(*pm,*pl);
-                        if (@comp@(*pr,*pm)) SWAP(*pr,*pm);
-                        if (@comp@(*pm,*pl)) SWAP(*pm,*pl);
+                        if (@lessthan@(*pm,*pl)) SWAP(*pm,*pl);
+                        if (@lessthan@(*pr,*pm)) SWAP(*pr,*pm);
+                        if (@lessthan@(*pm,*pl)) SWAP(*pm,*pl);
                         vp = *pm;
                         pi = pl;
                         pj = pr - 1;
                         SWAP(*pm,*pj);
                         for(;;) {
-                                do ++pi; while (@comp@(*pi,vp));
-                                do --pj; while (@comp@(vp,*pj));
+                                do ++pi; while (@lessthan@(*pi,vp));
+                                do --pj; while (@lessthan@(vp,*pj));
                                 if (pi >= pj)  break;
                                 SWAP(*pi,*pj);
                         }
@@ -62,7 +63,8 @@ static void
                 /* insertion sort */
                 for(pi = pl + 1; pi <= pr; ++pi) {
                         vp = *pi;
-                        for(pj = pi, pt = pi - 1; pj > pl && @comp@(vp, *pt);) {
+                        for(pj = pi, pt = pi - 1; \
+			    pj > pl && @lessthan@(vp, *pt);) {
                                 *pj-- = *pt--;
                         }
                         *pj = vp;
@@ -71,10 +73,11 @@ static void
                 pr = *(--sptr);
                 pl = *(--sptr);
         }
+	return 0;
 }
 
-static void 
-@TYPE@_aquicksort(@type@ *v, intp* tosort, intp num, int elsize, void *unused)
+static int
+@TYPE@_aquicksort(@type@ *v, intp* tosort, intp num, void *unused)
 {
 	@type@ vp;
 	intp *pl, *pr, SWAP_temp;
@@ -87,16 +90,16 @@ static void
                 while ((pr - pl) > 15) {
                         /* quicksort partition */
                         pm = pl + ((pr - pl) >> 1);
-                        if (@comp@(v[*pm],v[*pl])) SWAP(*pm,*pl);
-                        if (@comp@(v[*pr],v[*pm])) SWAP(*pr,*pm);
-                        if (@comp@(v[*pm],v[*pl])) SWAP(*pm,*pl);
+                        if (@lessthan@(v[*pm],v[*pl])) SWAP(*pm,*pl);
+                        if (@lessthan@(v[*pr],v[*pm])) SWAP(*pr,*pm);
+                        if (@lessthan@(v[*pm],v[*pl])) SWAP(*pm,*pl);
                         vp = v[*pm];
                         pi = pl;
                         pj = pr - 1;
                         SWAP(*pm,*pj);
                         for(;;) {
-                                do ++pi; while (@comp@(v[*pi],vp));
-                                do --pj; while (@comp@(vp,v[*pj]));
+                                do ++pi; while (@lessthan@(v[*pi],vp));
+                                do --pj; while (@lessthan@(vp,v[*pj]));
                                 if (pi >= pj)  break;
                                 SWAP(*pi,*pj);
                         }
@@ -116,7 +119,8 @@ static void
                 for(pi = pl + 1; pi <= pr; ++pi) {
                         vi = *pi;
                         vp = v[vi];
-                        for(pj = pi, pt = pi - 1; pj > pl && @comp@(vp, v[*pt]);)
+                        for(pj = pi, pt = pi - 1; \
+			    pj > pl && @lessthan@(vp, v[*pt]);)
 				{
 					*pj-- = *pt--;
 				}
@@ -126,6 +130,207 @@ static void
                 pr = *(--sptr);
                 pl = *(--sptr);
         }
+	return 0;
+}
+
+static void
+@TYPE@_mergesort0(@type@ *pl, @type@ *pr, @type@ *pw)
+{
+	@type@ vp, *pi, *pj, *pk, *pm;
+
+        if (pr - pl > 20) {
+                /* merge sort */
+                pm = pl + ((pr - pl + 1)>>1);
+                @TYPE@_mergesort0(pl,pm-1,pw);
+                @TYPE@_mergesort0(pm,pr,pw);
+                for(pi = pw, pj = pl; pj < pm; ++pi, ++pj) {
+                        *pi = *pj;
+                }
+                for(pk = pw, pm = pl; pk < pi && pj <= pr; ++pm) {
+                        if (@lessequal@(*pk,*pj)) {
+                                *pm = *pk;
+                                ++pk;
+                        }else{
+                                *pm = *pj;
+                                ++pj;
+                        }
+                }
+                for(; pk < pi; ++pm, ++pk) {
+                        *pm = *pk;
+                }
+        }else{
+                /* insertion sort */
+                for(pi = pl + 1; pi <= pr; ++pi) {
+                        vp = *pi;
+                        for(pj = pi, pk = pi - 1;\
+			    pj > pl && @lessthan@(vp, *pk); --pj, --pk) {
+                                *pj = *pk;
+                        }
+                        *pj = vp;
+                }
+        }
+}
+
+static int
+@TYPE@_mergesort(@type@ *start, intp num, void *unused)
+{
+	@type@ *pl, *pr, *pw;
+
+	pl = start; pr = pl + num - 1;
+	pw = (@type@ *) PyDataMem_NEW(((1+num/2))*sizeof(@type@));
+	
+	if (!pw) {
+		PyErr_NoMemory();
+		return -1;
+	}
+
+	@TYPE@_mergesort0(pl, pr, pw);
+	PyDataMem_FREE(pw);
+	return 0;
+}
+
+static void 
+@TYPE@_amergesort0(intp *pl, intp *pr, @type@ *v, intp *pw)
+{
+        @type@ vp;
+        intp vi, *pi, *pj, *pk, *pm;
+
+        if (pr - pl > 20) {
+                /* merge sort */
+                pm = pl + ((pr - pl + 1)>>1);
+                @TYPE@_amergesort0(pl,pm-1,v,pw);
+                @TYPE@_amergesort0(pm,pr,v,pw);
+                for(pi = pw, pj = pl; pj < pm; ++pi, ++pj) {
+                        *pi = *pj;
+                }
+                for(pk = pw, pm = pl; pk < pi && pj <= pr; ++pm) {
+                        if (@lessequal@(v[*pk],v[*pj])) {
+                                *pm = *pk;
+                                ++pk;
+                        }else{
+                                *pm = *pj;
+                                ++pj;
+                        }
+                }
+                for(; pk < pi; ++pm, ++pk) {
+                        *pm = *pk;
+                }
+        }else{
+                /* insertion sort */
+                for(pi = pl + 1; pi <= pr; ++pi) {
+                        vi = *pi;
+                        vp = v[vi];
+                        for(pj = pi, pk = pi - 1;			\
+			    pj > pl && @lessthan@(vp, v[*pk]); --pj, --pk) {
+                                *pj = *pk;
+                        }
+                        *pj = vi;
+                }
+        }
+}
+
+static int
+@TYPE@_amergesort(@type@ *v, intp *tosort, intp num, void *unused)
+{
+	intp *pl, *pr, *pw;
+
+	pl = tosort; pr = pl + num - 1;
+	pw = PyDimMem_NEW((1+num/2));
+	
+	if (!pw) {
+		PyErr_NoMemory();
+		return -1;
+	}
+
+	@TYPE@_amergesort0(pl, pr, v, pw);
+	PyDimMem_FREE(pw);
+	return 0;
+}
+
+static int
+@TYPE@_heapsort(@type@ *start, intp n, void *unused)
+{
+	
+        @type@ tmp, *a;
+        intp i,j,l;
+
+        /* The array needs to be offset by one for heapsort indexing */
+	a = start - 1;
+
+        for (l = n>>1; l > 0; --l) {
+                tmp = a[l];
+                for (i = l, j = l<<1; j <= n;) {
+                        if (j < n && @lessthan@(a[j], a[j+1]))
+                                j += 1;
+                        if (@lessthan@(tmp, a[j])) {
+                                a[i] = a[j];
+                                i = j;
+                                j += j;
+                        }else
+                                break;
+                }
+                a[i] = tmp;
+        }
+
+        for (; n > 1;) {
+                tmp = a[n];
+                a[n] = a[1];
+                n -= 1;
+                for (i = 1, j = 2; j <= n;) {
+                        if (j < n && @lessthan@(a[j], a[j+1]))
+                                j++;
+                        if (@lessthan@(tmp, a[j])) {
+                                a[i] = a[j];
+                                i = j;
+                                j += j;
+                        }else
+                                break;
+                }
+                a[i] = tmp;
+        }
+	return 0;
+}
+
+static int
+@TYPE@_aheapsort(@type@ *v, intp *tosort, intp n, void *unused)
+{
+	intp *a, i,j,l, tmp;
+	/* The arrays need to be offset by one for heapsort indexing */
+	a = tosort - 1;
+
+        for (l = n>>1; l > 0; --l) {
+                tmp = a[l];
+                for (i = l, j = l<<1; j <= n;) {
+                        if (j < n && @lessthan@(v[a[j]], v[a[j+1]]))
+                                j += 1;
+                        if (@lessthan@(v[tmp], v[a[j]])) {
+                                a[i] = a[j];
+                                i = j;
+                                j += j;
+                        }else
+                                break;
+                }
+                a[i] = tmp;
+        }
+
+        for (; n > 1;) {
+                tmp = a[n];
+                a[n] = a[1];
+                n -= 1;
+                for (i = 1, j = 2; j <= n;) {
+                        if (j < n && @lessthan@(v[a[j]], v[a[j+1]]))
+                                j++;
+                        if (@lessthan@(v[tmp], v[a[j]])) {
+                                a[i] = a[j];
+                                i = j;
+                                j += j;
+                        }else
+                                break;
+                }
+                a[i] = tmp;
+        }
+
+	return 0;
 }
 /**end repeat**/
 	
@@ -138,8 +343,18 @@ add_sortfuncs(void)
 #TYPE=BOOL,BYTE,UBYTE,SHORT,USHORT,INT,UINT,LONG,ULONG,LONGLONG,ULONGLONG,FLOAT,DOUBLE,LONGDOUBLE,CFLOAT,CDOUBLE,CLONGDOUBLE#
 **/
 	descr = PyArray_DescrFromType(PyArray_@TYPE@);
-	descr->f->sort[PyArray_QUICKSORT] = (PyArray_SortFunc *)@TYPE@_quicksort;
-	descr->f->argsort[PyArray_QUICKSORT] = (PyArray_ArgSortFunc *)@TYPE@_aquicksort;
+	descr->f->sort[PyArray_QUICKSORT] = \
+		(PyArray_SortFunc *)@TYPE@_quicksort;
+	descr->f->argsort[PyArray_QUICKSORT] = \
+		(PyArray_ArgSortFunc *)@TYPE@_aquicksort;
+	descr->f->sort[PyArray_HEAPSORT] = \
+		(PyArray_SortFunc *)@TYPE@_heapsort;
+	descr->f->argsort[PyArray_HEAPSORT] = \
+		(PyArray_ArgSortFunc *)@TYPE@_aheapsort;
+	descr->f->sort[PyArray_MERGESORT] = \
+		(PyArray_SortFunc *)@TYPE@_mergesort;
+	descr->f->argsort[PyArray_MERGESORT] = \
+		(PyArray_ArgSortFunc *)@TYPE@_amergesort;
 /**end repeat**/
 }
 
diff --git a/scipy/base/src/arraymethods.c b/scipy/base/src/arraymethods.c
index 786e116bd..3d2889e9e 100644
--- a/scipy/base/src/arraymethods.c
+++ b/scipy/base/src/arraymethods.c
@@ -709,36 +709,44 @@ array_choose(PyArrayObject *self, PyObject *args)
 	return _ARET(PyArray_Choose(self, choices));
 }
 
-static char doc_sort[] = "a.sort(<-1>) sorts in place along axis.  Return is None.";
+static char doc_sort[] = "a.sort(axis=-1,kind='quicksort') sorts in place along axis.  Return is None and kind can be 'quicksort', 'mergesort', or 'heapsort'";
 
 static PyObject *
-array_sort(PyArrayObject *self, PyObject *args) 
+array_sort(PyArrayObject *self, PyObject *args, PyObject *kwds) 
 {
 	int axis=-1;
 	int val;
+	PyArray_SORTKIND which=PyArray_QUICKSORT;
+	static char *kwlist[] = {"axis", "kind", NULL};
 	
-	if (!PyArg_ParseTuple(args, "|O&", PyArray_AxisConverter, 
-			      &axis)) return NULL;
+	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O&O&", kwlist, 
+					 PyArray_AxisConverter, &axis,
+					 PyArray_SortkindConverter, &which))
+		return NULL;
 	
-	val = PyArray_Sort(self, axis, PyArray_QUICKSORT);
+	val = PyArray_Sort(self, axis, which);
 	if (val < 0) return NULL;
 	Py_INCREF(Py_None);
 	return Py_None;
 }
 
-static char doc_argsort[] = "a.argsort(<-1>)\n"\
+static char doc_argsort[] = "a.argsort(axis=-1,kind='quicksort')\n"\
 	"  Return the indexes into a that would sort it along the"\
-	"  given axis";
+	"  given axis; kind can be 'quicksort', 'mergesort', or 'heapsort'";
 
 static PyObject *
-array_argsort(PyArrayObject *self, PyObject *args) 
+array_argsort(PyArrayObject *self, PyObject *args, PyObject *kwds) 
 {
 	int axis=-1;
+	PyArray_SORTKIND which=PyArray_QUICKSORT;
+	static char *kwlist[] = {"axis", "kind", NULL};
 	
-	if (!PyArg_ParseTuple(args, "|O&", PyArray_AxisConverter, 
-			      &axis)) return NULL;
+	if (!PyArg_ParseTupleAndKeywords(args, kwds, "|O&O&", kwlist, 
+					 PyArray_AxisConverter, &axis,
+					 PyArray_SortkindConverter, &which))
+		return NULL;
 	
-	return _ARET(PyArray_ArgSort(self, axis, PyArray_QUICKSORT));
+	return _ARET(PyArray_ArgSort(self, axis, which));
 }
 
 static char doc_searchsorted[] = "a.searchsorted(v)\n"\
@@ -1570,9 +1578,9 @@ static PyMethodDef array_methods[] = {
 	{"choose",	(PyCFunction)array_choose, 
 	 METH_VARARGS, doc_choose},	
 	{"sort",	(PyCFunction)array_sort, 
-	 METH_VARARGS, doc_sort},
+	 METH_VARARGS|METH_KEYWORDS, doc_sort},
 	{"argsort",	(PyCFunction)array_argsort, 
-	 METH_VARARGS, doc_argsort},
+	 METH_VARARGS|METH_KEYWORDS, doc_argsort},
 	{"searchsorted",  (PyCFunction)array_searchsorted, 
 	 METH_VARARGS, doc_searchsorted},	
 	{"argmax",	(PyCFunction)array_argmax, 
diff --git a/scipy/base/src/multiarraymodule.c b/scipy/base/src/multiarraymodule.c
index af6acfc34..4299adfb2 100644
--- a/scipy/base/src/multiarraymodule.c
+++ b/scipy/base/src/multiarraymodule.c
@@ -1591,9 +1591,12 @@ _new_sort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 	int elsize;
 	intp astride;
 	PyArray_SortFunc *sort;
+	BEGIN_THREADS_DEF 
 
 	it = (PyArrayIterObject *)PyArray_IterAllButAxis((PyObject *)op, axis);
 	if (it == NULL) return -1;
+
+	BEGIN_THREADS
 	sort = op->descr->f->sort[which];
 	size = it->size;
 	N = op->dimensions[axis];
@@ -1606,21 +1609,32 @@ _new_sort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 		char *buffer;
 		buffer = PyDataMem_NEW(N*elsize);
 		while (size--) {
-			_strided_copy(buffer, (intp) elsize, it->dataptr, astride, 
-				      N, elsize);
-			sort(buffer, N, elsize, op);
-			_strided_copy(it->dataptr, astride, buffer, (intp) elsize, 
-				      N, elsize);
+			_strided_copy(buffer, (intp) elsize, it->dataptr, 
+				      astride, N, elsize);
+			if (sort(buffer, N, op) < 0) {
+				PyDataMem_FREE(buffer); goto fail;
+			}
+			_strided_copy(it->dataptr, astride, buffer, 
+				      (intp) elsize, N, elsize);
 			PyArray_ITER_NEXT(it);
 		}
 		PyDataMem_FREE(buffer);
 	}
 	else {
 		while (size--) {
-			sort(it->dataptr, N, elsize, op);
+			if (sort(it->dataptr, N, op) < 0) goto fail;
 			PyArray_ITER_NEXT(it);
 		}
 	}	
+	
+	END_THREADS
+	
+	Py_DECREF(it);
+	return 0;
+
+ fail:
+	END_THREADS
+
 	Py_DECREF(it);
 	return 0;
 }
@@ -1637,6 +1651,7 @@ _new_argsort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 	int elsize;
 	intp astride, rstride, *iptr;
 	PyArray_ArgSortFunc *argsort;
+	BEGIN_THREADS_DEF 
 
 	ret = PyArray_New(op->ob_type, op->nd,
 			  op->dimensions, PyArray_INTP,
@@ -1646,6 +1661,9 @@ _new_argsort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 	it = (PyArrayIterObject *)PyArray_IterAllButAxis((PyObject *)op, axis);
 	rit = (PyArrayIterObject *)PyArray_IterAllButAxis(ret, axis);
 	if (rit == NULL || it == NULL) goto fail;
+
+	BEGIN_THREADS
+
 	argsort = op->descr->f->argsort[which];
 	size = it->size;
 	N = op->dimensions[axis];
@@ -1661,13 +1679,15 @@ _new_argsort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 		valbuffer = PyDataMem_NEW(N*(elsize+sizeof(intp)));
 		indbuffer = valbuffer + (N*elsize);
 		while (size--) {
-			_strided_copy(valbuffer, (intp) elsize, it->dataptr, astride, 
-				      N, elsize);
+			_strided_copy(valbuffer, (intp) elsize, it->dataptr,
+				      astride, N, elsize);
 			iptr = (intp *)indbuffer;
 			for (i=0; i<N; i++) *iptr++ = i;
-			argsort(valbuffer, (intp *)indbuffer, N, elsize, op);
-			_strided_copy(rit->dataptr, rstride, indbuffer, sizeof(intp),
-				      N, sizeof(intp));
+			if (argsort(valbuffer, (intp *)indbuffer, N, op) < 0) {
+				PyDataMem_FREE(valbuffer); goto fail;
+			}
+			_strided_copy(rit->dataptr, rstride, indbuffer, 
+				      sizeof(intp), N, sizeof(intp));
 			PyArray_ITER_NEXT(it);
 			PyArray_ITER_NEXT(rit);
 		}
@@ -1677,17 +1697,23 @@ _new_argsort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 		while (size--) {
 			iptr = (intp *)rit->dataptr;
 			for (i=0; i<N; i++) *iptr++ = i;
-			argsort(it->dataptr, (intp *)rit->dataptr, N, elsize, op);
+			if (argsort(it->dataptr, (intp *)rit->dataptr, 
+				    N, op) < 0)  goto fail;
 			PyArray_ITER_NEXT(it);
 			PyArray_ITER_NEXT(rit);
 		}
 	}
+	
+	END_THREADS
 
 	Py_DECREF(it);
 	Py_DECREF(rit);
 	return ret;
 
  fail:
+
+	END_THREADS
+
 	Py_DECREF(ret);
 	Py_XDECREF(it);
 	Py_XDECREF(rit);
@@ -1765,6 +1791,8 @@ PyArray_Sort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 	int i, n, m, elsize, orign;
 
 	n = op->nd;
+	if ((n==0) || (PyArray_SIZE(op)==1)) return 0;
+
 	if (axis < 0) axis += n;
 	if ((axis < 0) || (axis >= n)) {
 		PyErr_Format(PyExc_ValueError, 
@@ -1851,6 +1879,16 @@ PyArray_ArgSort(PyArrayObject *op, int axis, PyArray_SORTKIND which)
 	char *store_ptr;
 
 	n = op->nd;
+	if ((n==0) || (PyArray_SIZE(op)==1)) {
+		ret = (PyArrayObject *)PyArray_New(op->ob_type, op->nd,
+						   op->dimensions, 
+						   PyArray_INTP,
+						   NULL, NULL, 0, 0, 
+						   (PyObject *)op);
+		if (ret == NULL) return NULL;
+		*((intp *)ret->data) = 0;
+		return (PyObject *)ret;
+	}
 	if (axis < 0) axis += n;
 	if ((axis < 0) || (axis >= n)) {
 		PyErr_Format(PyExc_ValueError, 
@@ -3773,6 +3811,39 @@ PyArray_ByteorderConverter(PyObject *obj, char *endian)
 	return PY_SUCCEED;
 }
 
+/*MULTIARRAY_API
+  Convert object to sort kind 
+*/
+static int
+PyArray_SortkindConverter(PyObject *obj, PyArray_SORTKIND *sortkind)
+{
+	char *str;
+	*sortkind = PyArray_QUICKSORT;
+	str = PyString_AsString(obj);
+	if (!str) return PY_FAIL;
+	if (strlen(str) < 1) {
+		PyErr_SetString(PyExc_ValueError, 
+				"Sort kind string must be at least length 1");
+		return PY_FAIL;
+	}
+	if (str[0] == 'q' || str[0] == 'Q')
+		*sortkind = PyArray_QUICKSORT;
+	else if (str[0] == 'h' || str[0] == 'H')
+		*sortkind = PyArray_HEAPSORT;
+	else if (str[0] == 'm' || str[0] == 'M')
+		*sortkind = PyArray_MERGESORT;
+	else if (str[0] == 't' || str[0] == 'T')
+		*sortkind = PyArray_TIMSORT;
+	else {
+		PyErr_Format(PyExc_ValueError, 
+			     "%s is an unrecognized kind of sort",
+			     str);
+		return PY_FAIL;
+	}
+	return PY_SUCCEED;
+}
+
+
 /* This function returns true if the two typecodes are 
    equivalent (same basic kind and same itemsize).
 */
diff --git a/scipy/base/src/scalartypes.inc.src b/scipy/base/src/scalartypes.inc.src
index 19f1125ff..629adbcf0 100644
--- a/scipy/base/src/scalartypes.inc.src
+++ b/scipy/base/src/scalartypes.inc.src
@@ -1036,7 +1036,7 @@ gentype_wraparray(PyObject *scalar, PyObject *args)
 
 /**begin repeat
 
-#name=tolist, item, tostring, astype, copy, resize, __deepcopy__, choose, sort, argsort, searchsorted, argmax, argmin, reshape, view, swapaxes, max, min, ptp, conj, conjugate, nonzero, all, any, flatten, ravel, fill, transpose, newbyteorder#
+#name=tolist, item, tostring, astype, copy, resize, __deepcopy__, choose, searchsorted, argmax, argmin, reshape, view, swapaxes, max, min, ptp, conj, conjugate, nonzero, all, any, flatten, ravel, fill, transpose, newbyteorder#
 */
 
 static PyObject *
@@ -1095,7 +1095,7 @@ gentype_byteswap(PyObject *self, PyObject *args)
 
 /**begin repeat
 
-#name=take, getfield, put, putmask, repeat, tofile, mean, trace, diagonal, clip, std, var, sum, cumsum, prod, cumprod, compress#
+#name=take, getfield, put, putmask, repeat, tofile, mean, trace, diagonal, clip, std, var, sum, cumsum, prod, cumprod, compress, sort, argsort#
 */
 
 static PyObject *