diff options
author | Charles Harris <charlesr.harris@gmail.com> | 2019-02-08 17:45:28 -0700 |
---|---|---|
committer | Charles Harris <charlesr.harris@gmail.com> | 2019-02-08 17:45:28 -0700 |
commit | 107e45b82021ba04f651f0ef89aa2f419d404d64 (patch) | |
tree | bb3b703b40de42e9fde20369d6a67680cf2e5dbe /doc | |
parent | d3eb626ef41e1302631b5154037567b9cc02630d (diff) | |
download | numpy-107e45b82021ba04f651f0ef89aa2f419d404d64.tar.gz |
DOC: Update sorting documention.
Update the sorting documentation to reflect the reality that 'mergesort'
and 'stable' are aliases and may refer to any of several stable sorting
algorithms depending on data type.
[ci skip]
Diffstat (limited to 'doc')
-rw-r--r-- | doc/changelog/1.15.0-changelog.rst | 2 | ||||
-rw-r--r-- | doc/release/1.17.0-notes.rst | 17 | ||||
-rw-r--r-- | doc/source/reference/c-api.array.rst | 37 |
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 |