add sort, partial_sort and binary_sort to libcpp.algorithm

2 files changed, 47 insertions, 1 deletions

diff --git a/Cython/Includes/libcpp/algorithm.pxd b/Cython/Includes/libcpp/algorithm.pxd
index bbf53eaf8..0c12bc6fe 100644
--- a/Cython/Includes/libcpp/algorithm.pxd
+++ b/Cython/Includes/libcpp/algorithm.pxd
@@ -1,4 +1,20 @@
+from libcpp cimport bool
+
+
 cdef extern from "<algorithm>" namespace "std" nogil:
+    # Sorting and searching
+    bool binary_search[Iter, T](Iter first, Iter last, const T& value)
+    bool binary_search[Iter, T, Compare](Iter first, Iter last, const T& value,
+                                         Compare comp)
+
+    void partial_sort[Iter](Iter first, Iter middle, Iter last)
+    void partial_sort[Iter, Compare](Iter first, Iter middle, Iter last,
+                                     Compare comp)
+
+    void sort[Iter](Iter first, Iter last)
+    void sort[Iter, Compare](Iter first, Iter last, Compare comp)
+
+    # Binary heaps (priority queues)
     void make_heap[Iter](Iter first, Iter last)
     void make_heap[Iter, Compare](Iter first, Iter last, Compare comp)
 
diff --git a/tests/run/libcpp_algo.pyx b/tests/run/libcpp_algo.pyx
index ec123b837..2b0a352fe 100644
--- a/tests/run/libcpp_algo.pyx
+++ b/tests/run/libcpp_algo.pyx
@@ -1,7 +1,7 @@
 # tag: cpp
 
 from libcpp cimport bool
-from libcpp.algorithm cimport make_heap, sort_heap
+from libcpp.algorithm cimport make_heap, sort_heap, sort, partial_sort
 from libcpp.vector cimport vector
 
 
@@ -27,3 +27,33 @@ def heapsort(l, bool reverse=False):
         sort_heap(v.begin(), v.end())
 
     return v
+
+
+def partialsort(l, int k, reverse=False):
+    """
+    >>> partialsort([4, 2, 3, 1, 5], k=2)[:2]
+    [1, 2]
+    >>> partialsort([4, 2, 3, 1, 5], k=2, reverse=True)[:2]
+    [5, 4]
+    """
+    cdef vector[int] v = l
+    if reverse:
+        partial_sort(v.begin(), v.begin() + k, v.end(), greater)
+    else:
+        partial_sort(v.begin(), v.begin() + k, v.end())
+    return v
+
+
+def stdsort(l, reverse=False):
+    """
+    >>> stdsort([3, 2, 1, 4, 5])
+    [1, 2, 3, 4, 5]
+    >>> stdsort([3, 2, 1, 4, 5], reverse=True)
+    [5, 4, 3, 2, 1]
+    """
+    cdef vector[int] v = l
+    if reverse:
+        sort(v.begin(), v.end(), greater)
+    else:
+        sort(v.begin(), v.end())
+    return v