Index: libcxx/benchmarks/CMakeLists.txt
===================================================================
--- libcxx/benchmarks/CMakeLists.txt
+++ libcxx/benchmarks/CMakeLists.txt
@@ -162,6 +162,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/common.h
===================================================================
--- libcxx/benchmarks/algorithms/common.h
+++ libcxx/benchmarks/algorithms/common.h
@@ -37,12 +37,13 @@
   PipeOrgan,
   Heap,
   QuickSortAdversary,
+  QuickSelectAdversary,
 };
-struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
+struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 8> {
   static constexpr const char* Names[] = {"Random",     "Ascending",
                                           "Descending", "SingleElement",
                                           "PipeOrgan",  "Heap",
-                                          "QuickSortAdversary"};
+                                          "QuickSortAdversary", "QuickSelectAdversary"};
 };
 
 // fillAdversarialQuickSortInput fills the input vector with N int-like values.
@@ -88,12 +89,34 @@
   });
 }
 
+// fillAdversarialQuickSelectInput fills the input vector with N int-like values.
+// These values are arranged in such a way that they will make quickselect using median
+// of 3 quadratic.
+template <class T>
+void fillAdversarialQuickSelectInput(T& V, size_t N) {
+  assert(N > 0);
+
+  V.reserve(N);
+  size_t K = N / 2;
+  for (size_t i = 0; i < K; ++i) {
+    if (i & 1) {
+      V.push_back(K + i - 1);
+    } else {
+      V.push_back(i);
+    }
+  }
+  for (size_t i = 0; i < K; ++i)
+    V.push_back(2 * i);
+}
+
 template <typename T>
 void fillValues(std::vector<T>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
     V.resize(N, 0);
   } else if (O == Order::QuickSortAdversary) {
     fillAdversarialQuickSortInput(V, N);
+  } else if (O == Order::QuickSelectAdversary) {
+    fillAdversarialQuickSelectInput(V, N);
   } else {
     while (V.size() < N)
       V.push_back(V.size());
@@ -172,6 +195,7 @@
     std::make_heap(V.begin(), V.end());
     break;
   case Order::QuickSortAdversary:
+  case Order::QuickSelectAdversary:
     // Nothing to do
     break;
   }
Index: libcxx/benchmarks/algorithms/nth_element.bench.cpp
===================================================================
--- /dev/null
+++ libcxx/benchmarks/algorithms/nth_element.bench.cpp
@@ -0,0 +1,43 @@
+//===----------------------------------------------------------------------===//
+//
+// 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 <random>
+
+#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::CountBatch,
+        [](auto& Copy) {
+            size_t k = Copy.size() / 2;
+            std::nth_element(Copy.begin(), Copy.begin() + k, Copy.end());
+        });
+  }
+
+  bool skip() const { return Order() == ::Order::QuickSelectAdversary && Quantity == 1; }
+
+  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();
+}
Index: libcxx/include/__algorithm/nth_element.h
===================================================================
--- libcxx/include/__algorithm/nth_element.h
+++ libcxx/include/__algorithm/nth_element.h
@@ -12,6 +12,8 @@
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
+#include <__algorithm/make_heap.h>
+#include <__algorithm/sift_down.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
@@ -41,6 +43,26 @@
     }
 }
 
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
+__heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
+{
+    std::__make_heap<_AlgPolicy>(__first, __middle, __comp);
+
+    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
+    _RandomAccessIterator __i = __middle;
+    for (; __i != __last; ++__i)
+    {
+        if (__comp(*__i, *__first))
+        {
+            _IterOps<_AlgPolicy>::iter_swap(__i, __first);
+            std::__sift_down<_AlgPolicy>(__first, __comp, __len, __first);
+        }
+    }
+
+    _IterOps<_AlgPolicy>::iter_swap(__first, __middle);
+}
+
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
@@ -50,6 +72,7 @@
     // _Compare is known to be a reference type
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     const difference_type __limit = 7;
+    difference_type __depth = 2 * std::__log2i(__last - __first);
     while (true)
     {
         if (__nth == __last)
@@ -76,6 +99,13 @@
             std::__selection_sort<_AlgPolicy, _Compare>(__first, __last, __comp);
             return;
         }
+        if (__depth == 0)
+        {
+            // fall back to heap select.
+            __heap_select<_AlgPolicy, _Compare>(__first, __nth, __last, __comp);
+            return;
+        }
+        --__depth;
         // __len > __limit >= 3
         _RandomAccessIterator __m = __first + __len/2;
         _RandomAccessIterator __lm1 = __last;
Index: libcxx/include/__algorithm/sort.h
===================================================================
--- libcxx/include/__algorithm/sort.h
+++ libcxx/include/__algorithm/sort.h
@@ -884,7 +884,7 @@
 }
 
 template <typename _Number>
-inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Number __log2i(_Number __n) {
   if (__n == 0)
     return 0;
   if (sizeof(__n) <= sizeof(unsigned))