From c3cea4558bb37ba1e6a7a045c108081a88a88691 Mon Sep 17 00:00:00 2001 From: Julian Taylor Date: Thu, 21 Jul 2016 21:44:27 +0200 Subject: 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)) --- numpy/core/fromnumeric.py | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'numpy/core/fromnumeric.py') 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]]) -- cgit v1.2.1