ENH: turn quicksort into introsort

Introsort is regular quicksort but changing to a heapsort when not
enough progress is made. This retains the good quicksort performance
while changing the worst case runtime from O(N^2) to O(N*log(N))

1 files changed, 6 insertions, 0 deletions

diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py
index 7e02ff2c2..d07c5c08b 100644
--- a/numpy/core/fromnumeric.py
+++ b/numpy/core/fromnumeric.py
@@ -776,6 +776,12 @@ def sort(a, axis=-1, kind='quicksort', order=None):
     placements are sorted according to the non-nan part if it exists.
     Non-nan values are sorted as before.
 
+    .. versionadded:: 1.12.0
+
+    quicksort has been changed to an introsort which will switch
+    heapsort when it does not make enough progress. This makes its
+    worst case O(n*log(n)).
+
     Examples
     --------
     >>> a = np.array([[1,4],[3,1]])