DOC: add docstring for timsort

4 files changed, 24 insertions, 7 deletions

diff --git a/doc/release/1.17.0-notes.rst b/doc/release/1.17.0-notes.rst
index 4bdb812d7..f40b03a89 100644
--- a/doc/release/1.17.0-notes.rst
+++ b/doc/release/1.17.0-notes.rst
@@ -44,6 +44,14 @@ 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
+------------------------------------------------
+The ``kind`` keyword argument for ``sort`` and ``argsort`` now accepts ``'t'``
+or ``'timsort'`` for Timsort. Timsort features great performace
+on already or nearly sorted data and basically changes to Mergesort on random data.
+The algorithm is stable and requires O(n/2) additional 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 7c298e118..cf3c10e3b 100644
--- a/doc/source/reference/c-api.array.rst
+++ b/doc/source/reference/c-api.array.rst
@@ -2988,8 +2988,9 @@ to.
 .. c:function:: int PyArray_SortkindConverter(PyObject* obj, NPY_SORTKIND* sort)
 
     Convert Python strings into one of :c:data:`NPY_QUICKSORT` (starts
-    with 'q' or 'Q') , :c:data:`NPY_HEAPSORT` (starts with 'h' or 'H'),
-    or :c:data:`NPY_MERGESORT` (starts with 'm' or 'M').
+    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:function:: int PyArray_SearchsideConverter( \
         PyObject* obj, NPY_SEARCHSIDE* side)
@@ -3533,7 +3534,7 @@ Enumerated Types
     A special variable-type which can take on the values :c:data:`NPY_{KIND}`
     where ``{KIND}`` is
 
-        **QUICKSORT**, **HEAPSORT**, **MERGESORT**
+        **QUICKSORT**, **HEAPSORT**, **MERGESORT**, **TIMSORT**
 
     .. c:var:: NPY_NSORTS
 
diff --git a/numpy/core/_add_newdocs.py b/numpy/core/_add_newdocs.py
index 0727a72fe..ce23b2a16 100644
--- a/numpy/core/_add_newdocs.py
+++ b/numpy/core/_add_newdocs.py
@@ -3797,7 +3797,7 @@ add_newdoc('numpy.core.multiarray', 'ndarray', ('sort',
     axis : int, optional
         Axis along which to sort. Default is -1, which means sort along the
         last axis.
-    kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional
+    kind : {'quicksort', 'mergesort', 'heapsort', 'timsort', 'stable'}, optional
         Sorting algorithm. Default is 'quicksort'.
     order : str or list of str, optional
         When `a` is an array with fields defined, this argument specifies
diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py
index d94372986..7865dbf64 100644
--- a/numpy/core/fromnumeric.py
+++ b/numpy/core/fromnumeric.py
@@ -828,7 +828,7 @@ def sort(a, axis=-1, kind='quicksort', order=None):
     axis : int or None, optional
         Axis along which to sort. If None, the array is flattened before
         sorting. The default is -1, which sorts along the last axis.
-    kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional
+    kind : {'quicksort', 'mergesort', 'heapsort', 'timsort', 'stable'}, optional
         Sorting algorithm. Default is 'quicksort'.
     order : str or list of str, optional
         When `a` is an array with fields defined, this argument specifies
@@ -855,7 +855,7 @@ def sort(a, axis=-1, kind='quicksort', order=None):
     The various sorting algorithms are characterized by their average speed,
     worst case performance, work space size, and whether they are stable. A
     stable sort keeps items with the same key in the same relative
-    order. The three available algorithms have the following
+    order. The four available algorithms have the following
     properties:
 
     =========== ======= ============= ============ ========
@@ -864,6 +864,7 @@ def sort(a, axis=-1, kind='quicksort', order=None):
     'quicksort'    1     O(n^2)            0          no
     'mergesort'    2     O(n*log(n))      ~n/2        yes
     'heapsort'     3     O(n*log(n))       0          no
+    'timsort'      2     O(n*log(n))      ~n/2        yes
     =========== ======= ============= ============ ========
 
     All the sort algorithms make temporary copies of the data when
@@ -897,6 +898,13 @@ def sort(a, axis=-1, kind='quicksort', order=None):
     for the data type being sorted. It is currently mapped to
     merge sort.
 
+    .. versionadded:: 1.17.0
+    Timsort is added for better performance on already or nearly
+    sorted data. On random data timsort is almost identical to
+    mergesort. For details of timsort, refer to
+    `CPython listsort.txt <https://github.com/python/cpython/blob/3.7/Objects/listsort.txt>`_.
+
+
     Examples
     --------
     >>> a = np.array([[1,4],[3,1]])
@@ -959,7 +967,7 @@ def argsort(a, axis=-1, kind='quicksort', order=None):
     axis : int or None, optional
         Axis along which to sort.  The default is -1 (the last axis). If None,
         the flattened array is used.
-    kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional
+    kind : {'quicksort', 'mergesort', 'heapsort', 'timsort', 'stable'}, optional
         Sorting algorithm.
     order : str or list of str, optional
         When `a` is an array with fields defined, this argument specifies