Merge pull request #12945 from charris/fix-timsort-compat

BUG: Add timsort without breaking the API.

3 files changed, 32 insertions, 24 deletions

diff --git a/doc/changelog/1.15.0-changelog.rst b/doc/changelog/1.15.0-changelog.rst
index b76b9699a..4e3d3680b 100644
--- a/doc/changelog/1.15.0-changelog.rst
+++ b/doc/changelog/1.15.0-changelog.rst
@@ -374,7 +374,7 @@ A total of 438 pull requests were merged for this release.
 * `#10778 <https://github.com/numpy/numpy/pull/10778>`__: BUG: test, fix for missing flags['WRITEBACKIFCOPY'] key
 * `#10781 <https://github.com/numpy/numpy/pull/10781>`__: ENH: NEP index builder
 * `#10785 <https://github.com/numpy/numpy/pull/10785>`__: DOC: Fixed author name in reference to book
-* `#10786 <https://github.com/numpy/numpy/pull/10786>`__: ENH: Add "stablesort" option to inp.sort as an alias for "mergesort".
+* `#10786 <https://github.com/numpy/numpy/pull/10786>`__: ENH: Add "stable" option to np.sort as an alias for "mergesort".
 * `#10790 <https://github.com/numpy/numpy/pull/10790>`__: TST: Various fixes prior to switching to pytest
 * `#10795 <https://github.com/numpy/numpy/pull/10795>`__: BUG: Allow spaces in output string of einsum
 * `#10796 <https://github.com/numpy/numpy/pull/10796>`__: BUG: fix wrong inplace vectorization on overlapping arguments
diff --git a/doc/release/1.17.0-notes.rst b/doc/release/1.17.0-notes.rst
index ab09f85bd..d3a7779c8 100644
--- a/doc/release/1.17.0-notes.rst
+++ b/doc/release/1.17.0-notes.rst
@@ -54,14 +54,15 @@ identity, it is necessary to also pass in an initial value (e.g.,
 ``initial=np.inf`` for ``np.min``).  For instance, the equivalent of
 ``nansum`` would be, ``np.sum(a, where=~np.isnan(a))``.
 
-Timsort is added to available sorting algorithms and is now the default stable sort
------------------------------------------------------------------------------------
-The ``kind`` keyword argument for ``sort`` and ``argsort`` now accepts ``'t'``
-or ``'timsort'`` for Timsort. The ``stable`` option of ``kind`` argument is now
-mapped to Timsort. Timsort features great performace
-on already or nearly sorted data and resembles Mergesort on random data.
-The algorithm is stable and requires O(n/2) additional space.
-For details of the algorithm, refer to
+Timsort has replaced mergesort as the stable sorting implementation
+-------------------------------------------------------------------
+Timsort has been implemented and is now used in place of mergesort. Due to the
+need to maintain backward compatibility, the sorting ``kind`` options ``"stable"``
+and ``"mergesort"`` have been made aliases of each other with the actual sort
+implementation used a function of the array type. Timsort features improved
+performace on already or nearly sorted data and performs like mergesort on
+random data.  The algorithm is stable and requires O(n/2) working space.  For
+details of the algorithm, refer to
 `CPython listsort.txt <https://github.com/python/cpython/blob/3.7/Objects/listsort.txt>`_.
 
 ``np.linalg.svd`` and ``np.linalg.pinv`` can be faster on hermitian inputs
diff --git a/doc/source/reference/c-api.array.rst b/doc/source/reference/c-api.array.rst
index cf3c10e3b..44d09a9fe 100644
--- a/doc/source/reference/c-api.array.rst
+++ b/doc/source/reference/c-api.array.rst
@@ -1906,20 +1906,21 @@ Item selection and manipulation
 
 .. c:function:: PyObject* PyArray_Sort(PyArrayObject* self, int axis, NPY_SORTKIND kind)
 
-    Equivalent to :meth:`ndarray.sort<numpy.ndarray.sort>` (*self*, *axis*, *kind*). Return an array with
-    the items of *self* sorted along *axis*.Array is sorted according to *kind* which is an integer/enum pointing to the type of sorting algorithms used.
+    Equivalent to :meth:`ndarray.sort<numpy.ndarray.sort>` (*self*, *axis*, *kind*).
+    Return an array with the items of *self* sorted along *axis*. The array
+    is sorted using the algorithm denoted by *kind* , which is an integer/enum pointing
+    to the type of sorting algorithms used.
 
 .. c:function:: PyObject* PyArray_ArgSort(PyArrayObject* self, int axis)
 
-    Equivalent to :meth:`ndarray.argsort<numpy.ndarray.argsort>` (*self*, *axis*). Return an array of
-    indices such that selection of these indices along the given
-    ``axis`` would return a sorted version of *self*. If *self*
-    ->descr is a data-type with fields defined, then
-    self->descr->names is used to determine the sort order. A
-    comparison where the first field is equal will use the second
-    field and so on. To alter the sort order of a structured array, create
-    a new data-type with a different order of names and construct a
-    view of the array with that new data-type.
+    Equivalent to :meth:`ndarray.argsort<numpy.ndarray.argsort>` (*self*, *axis*).
+    Return an array of indices such that selection of these indices
+    along the given ``axis`` would return a sorted version of *self*. If *self* ->descr
+    is a data-type with fields defined, then self->descr->names is used
+    to determine the sort order. A comparison where the first field is equal
+    will use the second field and so on. To alter the sort order of a
+    structured array, create a new data-type with a different order of names
+    and construct a view of the array with that new data-type.
 
 .. c:function:: PyObject* PyArray_LexSort(PyObject* sort_keys, int axis)
 
@@ -2989,8 +2990,10 @@ to.
 
     Convert Python strings into one of :c:data:`NPY_QUICKSORT` (starts
     with 'q' or 'Q'), :c:data:`NPY_HEAPSORT` (starts with 'h' or 'H'),
-    :c:data:`NPY_MERGESORT` (starts with 'm' or 'M') or :c:data:`NPY_TIMSORT`
-    (starts with 't' or 'T').
+    :c:data:`NPY_MERGESORT` (starts with 'm' or 'M') or :c:data:`NPY_STABLESORT`
+    (starts with 't' or 'T'). :c:data:`NPY_MERGESORT` and :c:data:`NPY_STABLESORT`
+    are aliased to each other for backwards compatibility and may refer to one
+    of several stable sorting algorithms depending on the data type.
 
 .. c:function:: int PyArray_SearchsideConverter( \
         PyObject* obj, NPY_SEARCHSIDE* side)
@@ -3534,11 +3537,15 @@ Enumerated Types
     A special variable-type which can take on the values :c:data:`NPY_{KIND}`
     where ``{KIND}`` is
 
-        **QUICKSORT**, **HEAPSORT**, **MERGESORT**, **TIMSORT**
+        **QUICKSORT**, **HEAPSORT**, **MERGESORT**, **STABLESORT**
 
     .. c:var:: NPY_NSORTS
 
-       Defined to be the number of sorts.
+       Defined to be the number of sorts. It is fixed at three by the need for
+       backwards compatibility, and consequently :c:data:`NPY_MERGESORT` and
+       :c:data:`NPY_STABLESORT` are aliased to each other and may refer to one
+       of several stable sorting algorithms depending on the data type.
+
 
 .. c:type:: NPY_SCALARKIND