From 864a431fd6047b1c26a7001bd2e3d989a5320e0f Mon Sep 17 00:00:00 2001 From: Lakshay Garg Date: Fri, 23 Mar 2018 00:09:58 +0530 Subject: add stablesort in np.sort and point to mergesort Closes #10784 --- numpy/core/fromnumeric.py | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'numpy/core/fromnumeric.py') diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py index 10256c3c0..ddf3314cf 100644 --- a/numpy/core/fromnumeric.py +++ b/numpy/core/fromnumeric.py @@ -764,7 +764,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'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', '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 @@ -797,9 +797,10 @@ def sort(a, axis=-1, kind='quicksort', order=None): =========== ======= ============= ============ ======= kind speed worst case work space stable =========== ======= ============= ============ ======= - 'quicksort' 1 O(n^2) 0 no - 'mergesort' 2 O(n*log(n)) ~n/2 yes - 'heapsort' 3 O(n*log(n)) 0 no + 'quicksort' 1 O(n^2) 0 no + 'mergesort' 2 O(n*log(n)) ~n/2 yes + 'stable' 2 O(n*log(n)) ~n/2 yes + 'heapsort' 3 O(n*log(n)) 0 no =========== ======= ============= ============ ======= All the sort algorithms make temporary copies of the data when @@ -886,7 +887,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'}, optional + kind : {'quicksort', 'mergesort', 'heapsort', 'stable'}, optional Sorting algorithm. order : str or list of str, optional When `a` is an array with fields defined, this argument specifies -- cgit v1.2.1 From 4a2891748ab9ac8cafd7aaef10222c761e96f892 Mon Sep 17 00:00:00 2001 From: Lakshay Garg Date: Thu, 29 Mar 2018 12:39:30 +0530 Subject: Remove NPY_STABLESORT enum --- numpy/core/fromnumeric.py | 19 +++++++++++-------- 1 file changed, 11 insertions(+), 8 deletions(-) (limited to 'numpy/core/fromnumeric.py') diff --git a/numpy/core/fromnumeric.py b/numpy/core/fromnumeric.py index ddf3314cf..63279ffb3 100644 --- a/numpy/core/fromnumeric.py +++ b/numpy/core/fromnumeric.py @@ -794,14 +794,13 @@ def sort(a, axis=-1, kind='quicksort', order=None): order. The three available algorithms have the following properties: - =========== ======= ============= ============ ======= - kind speed worst case work space stable - =========== ======= ============= ============ ======= - 'quicksort' 1 O(n^2) 0 no - 'mergesort' 2 O(n*log(n)) ~n/2 yes - 'stable' 2 O(n*log(n)) ~n/2 yes - 'heapsort' 3 O(n*log(n)) 0 no - =========== ======= ============= ============ ======= + =========== ======= ============= ============ ======== + kind speed worst case work space stable + =========== ======= ============= ============ ======== + 'quicksort' 1 O(n^2) 0 no + 'mergesort' 2 O(n*log(n)) ~n/2 yes + 'heapsort' 3 O(n*log(n)) 0 no + =========== ======= ============= ============ ======== All the sort algorithms make temporary copies of the data when sorting along any but the last axis. Consequently, sorting along @@ -830,6 +829,10 @@ def sort(a, axis=-1, kind='quicksort', order=None): heapsort when it does not make enough progress. This makes its worst case O(n*log(n)). + 'stable' automatically choses the best stable sorting algorithm + for the data type being sorted. It is currently mapped to + merge sort. + Examples -------- >>> a = np.array([[1,4],[3,1]]) -- cgit v1.2.1