Merge pull request #12586 from hameerabbasi/radix-sort

ENH: Implement radix sort

1 files changed, 11 insertions, 0 deletions

diff --git a/doc/release/1.17.0-notes.rst b/doc/release/1.17.0-notes.rst
index 60614673f..80cb36a43 100644
--- a/doc/release/1.17.0-notes.rst
+++ b/doc/release/1.17.0-notes.rst
@@ -121,6 +121,9 @@ 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>`_.
 
+In addition, for very small dtypes, radix sort is used instead of timsort. In
+general, we attempt to use the fastest possible implementation.
+
 ``np.unpackbits`` now accepts a ``count`` parameter
 ---------------------------------------------------
 ``count`` allows subsetting the number of bits that will be unpacked up-front,
@@ -182,6 +185,14 @@ maintains `O(N log N)` run time complexity instead of deteriorating towards
 `O(N*N)` for prime lengths. Also, accuracy for real-valued FFTs with near-prime
 lengths has improved and is on par with complex-valued FFTs.
 
+Performance improvements for integer sorts
+------------------------------------------
+
+``sort``, ``argsort``, ``ndarray.sort`` and ``ndarray.argsort`` now use radix
+sort as the default stable sort for integers and booleans. This is faster than
+the old default, mergesort, in the vast majority of cases.
+
+
 Further improvements to ``ctypes`` support in ``np.ctypeslib``
 --------------------------------------------------------------
 A new `numpy.ctypeslib.as_ctypes_type` function has been added, which can be