Index: libcxx/benchmarks/CMakeLists.txt
===================================================================
--- libcxx/benchmarks/CMakeLists.txt
+++ libcxx/benchmarks/CMakeLists.txt
@@ -163,6 +163,7 @@
     algorithms/make_heap.bench.cpp
     algorithms/make_heap_then_sort_heap.bench.cpp
     algorithms/min_max_element.bench.cpp
+    algorithms/nth_element.bench.cpp
     algorithms/pop_heap.bench.cpp
     algorithms/push_heap.bench.cpp
     algorithms/ranges_make_heap.bench.cpp
Index: libcxx/benchmarks/algorithms/nth_element.bench.cpp
===================================================================
--- /dev/null
+++ libcxx/benchmarks/algorithms/nth_element.bench.cpp
@@ -0,0 +1,37 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct NthElement {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+      size_t k = Copy.size() / 2;
+      std::nth_element(Copy.begin(), Copy.begin() + k, Copy.end());
+    });
+  }
+
+  std::string name() const {
+    return "BM_NthElement" + ValueType::name() + Order::name() + "_" + std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<NthElement, AllValueTypes, AllOrders>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}
\ No newline at end of file
Index: libcxx/include/__algorithm/nth_element.h
===================================================================
--- libcxx/include/__algorithm/nth_element.h
+++ libcxx/include/__algorithm/nth_element.h
@@ -12,6 +12,7 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/min_element.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
@@ -25,6 +26,25 @@
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+// Implement partial sort base on selection sort. Rearranges elements such that the range [__first, __middle) contains
+// the sorted __middle - __first smallest elements in the range [__first, __last).
+// For selection sort, after each round, the position of element that __first represents is determined. That is, if we
+// end up when __first == __middle, [__first, __middle) contains the sorted __middle - __first smallest elements in the
+// range [__first, __last) already.
+template <class _AlgPolicy, class _Compare, class _BidirectionalIterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void __selection_partial_sort(
+    _BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp) {
+  // if [__first, __last - 1) is determined, then [__first, __last) is determined.
+  if (__middle == __last)
+    --__middle;
+
+  for (; __first != __middle; ++__first) {
+    _BidirectionalIterator __i = std::__min_element(__first, __last, __comp);
+    if (__i != __first)
+      _IterOps<_AlgPolicy>::iter_swap(__first, __i);
+  }
+}
+
 template<class _Compare, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool
 __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
@@ -73,7 +93,8 @@
         }
         if (__len <= __limit)
         {
-            std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
+            std::__selection_partial_sort<_AlgPolicy, _Compare>(__first, __nth + difference_type(1), __last, __comp);
+            // [__first, __nth) <= *__nth and *__nth <= (__nth, __last)
             return;
         }
         // __len > __limit >= 3