diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -38,18 +38,65 @@
   Descending,
   SingleElement,
   PipeOrgan,
-  Heap
+  Heap,
+  QuickSortAdversary,
 };
-struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
+struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 7> {
   static constexpr const char* Names[] = {"Random",     "Ascending",
                                           "Descending", "SingleElement",
-                                          "PipeOrgan",  "Heap"};
+                                          "PipeOrgan",  "Heap",
+                                          "QuickSortAdversary"};
 };
 
+// fillAdversarialQuickSortInput fills the input vector with N int-like values.
+// These values are arranged in such a way that they would invoke O(N^2)
+// behavior on any quick sort implementation that satisifies certain conditions.
+// Details are available in the following paper:
+// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
+// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
+// https://dl.acm.org/doi/10.5555/311868.311871.
+template <class T>
+void fillAdversarialQuickSortInput(T& V, size_t N) {
+  assert(N > 0);
+  // If an element is equal to gas, it indicates that the value of the element
+  // is still to be decided and may change over the course of time.
+  const int gas = N - 1;
+  V.resize(N);
+  for (int i = 0; i < N; ++i) {
+    V[i] = gas;
+  }
+  // Candidate for the pivot position.
+  int candidate = 0;
+  int nsolid = 0;
+  // Populate all positions in the generated input to gas.
+  std::vector<int> ascVals(V.size());
+  // Fill up with ascending values from 0 to V.size()-1.  These will act as
+  // indices into V.
+  std::iota(ascVals.begin(), ascVals.end(), 0);
+  std::sort(ascVals.begin(), ascVals.end(), [&](int x, int y) {
+    if (V[x] == gas && V[y] == gas) {
+      // We are comparing two inputs whose value is still to be decided.
+      if (x == candidate) {
+        V[x] = nsolid++;
+      } else {
+        V[y] = nsolid++;
+      }
+    }
+    if (V[x] == gas) {
+      candidate = x;
+    } else if (V[y] == gas) {
+      candidate = y;
+    }
+    return V[x] < V[y];
+  });
+}
+
 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 {
     while (V.size() < N)
       V.push_back(V.size());
@@ -128,6 +175,9 @@
   case Order::Heap:
     std::make_heap(V.begin(), V.end());
     break;
+  case Order::QuickSortAdversary:
+    // Nothing to do
+    break;
   }
 }
 
diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h
--- a/libcxx/include/__algorithm/sort.h
+++ b/libcxx/include/__algorithm/sort.h
@@ -262,195 +262,193 @@
 }
 
 template <class _Compare, class _RandomAccessIterator>
-void
-__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    const difference_type __limit = is_trivially_copy_constructible<value_type>::value &&
-                                    is_trivially_copy_assignable<value_type>::value ? 30 : 6;
-    while (true)
+void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+                 typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type __depth) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+  const difference_type __limit =
+      is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6;
+  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
+  while (true) {
+  __restart:
+    if (__depth == 0) {
+      // Fallback to heap sort as Introsort suggests.
+      _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+      return;
+    }
+    --__depth;
+    difference_type __len = __last - __first;
+    switch (__len) {
+    case 0:
+    case 1:
+      return;
+    case 2:
+      if (__comp(*--__last, *__first))
+        swap(*__first, *__last);
+      return;
+    case 3:
+      _VSTD::__sort3<_Compare>(__first, __first + 1, --__last, __comp);
+      return;
+    case 4:
+      _VSTD::__sort4<_Compare>(__first, __first + 1, __first + 2, --__last, __comp);
+      return;
+    case 5:
+      _VSTD::__sort5<_Compare>(__first, __first + 1, __first + 2, __first + 3, --__last, __comp);
+      return;
+    }
+    if (__len <= __limit) {
+      _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
+      return;
+    }
+    // __len > 5
+    _RandomAccessIterator __m = __first;
+    _RandomAccessIterator __lm1 = __last;
+    --__lm1;
+    unsigned __n_swaps;
     {
-    __restart:
-        difference_type __len = __last - __first;
-        switch (__len)
-        {
-        case 0:
-        case 1:
-            return;
-        case 2:
-            if (__comp(*--__last, *__first))
-                swap(*__first, *__last);
-            return;
-        case 3:
-            _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
-            return;
-        case 4:
-            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
-            return;
-        case 5:
-            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
-            return;
-        }
-        if (__len <= __limit)
-        {
-            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
-            return;
-        }
-        // __len > 5
-        _RandomAccessIterator __m = __first;
-        _RandomAccessIterator __lm1 = __last;
-        --__lm1;
-        unsigned __n_swaps;
-        {
-        difference_type __delta;
-        if (__len >= 1000)
-        {
-            __delta = __len/2;
-            __m += __delta;
-            __delta /= 2;
-            __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
-        }
-        else
-        {
-            __delta = __len/2;
-            __m += __delta;
-            __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
-        }
-        }
-        // *__m is median
-        // partition [__first, __m) < *__m and *__m <= [__m, __last)
-        // (this inhibits tossing elements equivalent to __m around unnecessarily)
-        _RandomAccessIterator __i = __first;
-        _RandomAccessIterator __j = __lm1;
-        // j points beyond range to be tested, *__m is known to be <= *__lm1
-        // The search going up is known to be guarded but the search coming down isn't.
-        // Prime the downward search with a guard.
-        if (!__comp(*__i, *__m))  // if *__first == *__m
-        {
-            // *__first == *__m, *__first doesn't go in first part
-            // manually guard downward moving __j against __i
-            while (true)
-            {
-                if (__i == --__j)
-                {
-                    // *__first == *__m, *__m <= all other elements
-                    // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
-                    ++__i;  // __first + 1
-                    __j = __last;
-                    if (!__comp(*__first, *--__j))  // we need a guard if *__first == *(__last-1)
-                    {
-                        while (true)
-                        {
-                            if (__i == __j)
-                                return;  // [__first, __last) all equivalent elements
-                            if (__comp(*__first, *__i))
-                            {
-                                swap(*__i, *__j);
-                                ++__n_swaps;
-                                ++__i;
-                                break;
-                            }
-                            ++__i;
-                        }
-                    }
-                    // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
-                    if (__i == __j)
-                        return;
-                    while (true)
-                    {
-                        while (!__comp(*__first, *__i))
-                            ++__i;
-                        while (__comp(*__first, *--__j))
-                            ;
-                        if (__i >= __j)
-                            break;
-                        swap(*__i, *__j);
-                        ++__n_swaps;
-                        ++__i;
-                    }
-                    // [__first, __i) == *__first and *__first < [__i, __last)
-                    // The first part is sorted, sort the second part
-                    // _VSTD::__sort<_Compare>(__i, __last, __comp);
-                    __first = __i;
-                    goto __restart;
-                }
-                if (__comp(*__j, *__m))
-                {
-                    swap(*__i, *__j);
-                    ++__n_swaps;
-                    break;  // found guard for downward moving __j, now use unguarded partition
-                }
-            }
-        }
-        // It is known that *__i < *__m
-        ++__i;
-        // j points beyond range to be tested, *__m is known to be <= *__lm1
-        // if not yet partitioned...
-        if (__i < __j)
-        {
-            // known that *(__i - 1) < *__m
-            // known that __i <= __m
-            while (true)
-            {
-                // __m still guards upward moving __i
-                while (__comp(*__i, *__m))
-                    ++__i;
-                // It is now known that a guard exists for downward moving __j
-                while (!__comp(*--__j, *__m))
-                    ;
-                if (__i > __j)
-                    break;
+      difference_type __delta;
+      if (__len >= 1000) {
+        __delta = __len / 2;
+        __m += __delta;
+        __delta /= 2;
+        __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp);
+      } else {
+        __delta = __len / 2;
+        __m += __delta;
+        __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
+      }
+    }
+    // *__m is median
+    // partition [__first, __m) < *__m and *__m <= [__m, __last)
+    // (this inhibits tossing elements equivalent to __m around unnecessarily)
+    _RandomAccessIterator __i = __first;
+    _RandomAccessIterator __j = __lm1;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // The search going up is known to be guarded but the search coming down isn't.
+    // Prime the downward search with a guard.
+    if (!__comp(*__i, *__m)) // if *__first == *__m
+    {
+      // *__first == *__m, *__first doesn't go in first part
+      // manually guard downward moving __j against __i
+      while (true) {
+        if (__i == --__j) {
+          // *__first == *__m, *__m <= all other elements
+          // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
+          ++__i; // __first + 1
+          __j = __last;
+          if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
+          {
+            while (true) {
+              if (__i == __j)
+                return; // [__first, __last) all equivalent elements
+              if (__comp(*__first, *__i)) {
                 swap(*__i, *__j);
                 ++__n_swaps;
-                // It is known that __m != __j
-                // If __m just moved, follow it
-                if (__m == __i)
-                    __m = __j;
                 ++__i;
+                break;
+              }
+              ++__i;
             }
-        }
-        // [__first, __i) < *__m and *__m <= [__i, __last)
-        if (__i != __m && __comp(*__m, *__i))
-        {
-            swap(*__i, *__m);
+          }
+          // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
+          if (__i == __j)
+            return;
+          while (true) {
+            while (!__comp(*__first, *__i))
+              ++__i;
+            while (__comp(*__first, *--__j))
+              ;
+            if (__i >= __j)
+              break;
+            swap(*__i, *__j);
             ++__n_swaps;
+            ++__i;
+          }
+          // [__first, __i) == *__first and *__first < [__i, __last)
+          // The first part is sorted, sort the second part
+          // _VSTD::__sort<_Compare>(__i, __last, __comp);
+          __first = __i;
+          goto __restart;
         }
-        // [__first, __i) < *__i and *__i <= [__i+1, __last)
-        // If we were given a perfect partition, see if insertion sort is quick...
-        if (__n_swaps == 0)
-        {
-            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
-            if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp))
-            {
-                if (__fs)
-                    return;
-                __last = __i;
-                continue;
-            }
-            else
-            {
-                if (__fs)
-                {
-                    __first = ++__i;
-                    continue;
-                }
-            }
-        }
-        // sort smaller range with recursive call and larger with tail recursion elimination
-        if (__i - __first < __last - __i)
-        {
-            _VSTD::__sort<_Compare>(__first, __i, __comp);
-            // _VSTD::__sort<_Compare>(__i+1, __last, __comp);
-            __first = ++__i;
+        if (__comp(*__j, *__m)) {
+          swap(*__i, *__j);
+          ++__n_swaps;
+          break; // found guard for downward moving __j, now use unguarded partition
         }
-        else
-        {
-            _VSTD::__sort<_Compare>(__i+1, __last, __comp);
-            // _VSTD::__sort<_Compare>(__first, __i, __comp);
-            __last = __i;
+      }
+    }
+    // It is known that *__i < *__m
+    ++__i;
+    // j points beyond range to be tested, *__m is known to be <= *__lm1
+    // if not yet partitioned...
+    if (__i < __j) {
+      // known that *(__i - 1) < *__m
+      // known that __i <= __m
+      while (true) {
+        // __m still guards upward moving __i
+        while (__comp(*__i, *__m))
+          ++__i;
+        // It is now known that a guard exists for downward moving __j
+        while (!__comp(*--__j, *__m))
+          ;
+        if (__i > __j)
+          break;
+        swap(*__i, *__j);
+        ++__n_swaps;
+        // It is known that __m != __j
+        // If __m just moved, follow it
+        if (__m == __i)
+          __m = __j;
+        ++__i;
+      }
+    }
+    // [__first, __i) < *__m and *__m <= [__i, __last)
+    if (__i != __m && __comp(*__m, *__i)) {
+      swap(*__i, *__m);
+      ++__n_swaps;
+    }
+    // [__first, __i) < *__i and *__i <= [__i+1, __last)
+    // If we were given a perfect partition, see if insertion sort is quick...
+    if (__n_swaps == 0) {
+      bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
+      if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + 1, __last, __comp)) {
+        if (__fs)
+          return;
+        __last = __i;
+        continue;
+      } else {
+        if (__fs) {
+          __first = ++__i;
+          continue;
         }
+      }
+    }
+    // sort smaller range with recursive call and larger with tail recursion elimination
+    if (__i - __first < __last - __i) {
+      _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth);
+      __first = ++__i;
+    } else {
+      _VSTD::__introsort<_Compare>(__i + 1, __last, __comp, __depth);
+      __last = __i;
     }
+  }
+}
+
+template <typename _Number>
+inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) {
+  _Number __log2 = 0;
+  while (__n > 1) {
+    __log2++;
+    __n >>= 1;
+  }
+  return __log2;
+}
+
+template <class _Compare, class _RandomAccessIterator>
+void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
+  difference_type __depth_limit = 2 * __log2i(__last - __first);
+  __introsort(__first, __last, __comp, __depth_limit);
 }
 
 template <class _Compare, class _Tp>
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp
@@ -147,6 +147,63 @@
     assert(*pv[array_size - 1] == v[array_size - 1]);
 }
 
+// test_adversarial_quicksort generates a vector with values arranged in such a
+// way that they would invoke O(N^2) behavior on any quick sort implementation
+// that satisifies certain conditions.  Details are available in the following
+// paper:
+// "A Killer Adversary for Quicksort", M. D. McIlroy, Software—Practice &
+// ExperienceVolume 29 Issue 4 April 10, 1999 pp 341–344.
+// https://dl.acm.org/doi/10.5555/311868.311871.
+struct AdversaryComparator {
+  AdversaryComparator(int N, std::vector<int>& input) : gas(N - 1), V(input) {
+    V.resize(N);
+    // Populate all positions in the generated input to gas to indicate that
+    // none of the values have been fixed yet.
+    for (int i = 0; i < N; ++i)
+      V[i] = gas;
+  }
+
+  bool operator()(int x, int y) {
+    if (V[x] == gas && V[y] == gas) {
+      // We are comparing two inputs whose value is still to be decided.
+      if (x == candidate) {
+        V[x] = nsolid++;
+      } else {
+        V[y] = nsolid++;
+      }
+    }
+    if (V[x] == gas) {
+      candidate = x;
+    } else if (V[y] == gas) {
+      candidate = y;
+    }
+    return V[x] < V[y];
+  }
+
+private:
+  // If an element is equal to gas, it indicates that the value of the element
+  // is still to be decided and may change over the course of time.
+  const int gas;
+  // This is a reference so that we can manipulate the input vector later.
+  std::vector<int>& V;
+  // Candidate for the pivot position.
+  int candidate = 0;
+  int nsolid = 0;
+};
+
+void test_adversarial_quicksort(int N) {
+  assert(N > 0);
+  std::vector<int> ascVals(N);
+  // Fill up with ascending values from 0 to N-1.  These will act as indices
+  // into V.
+  std::iota(ascVals.begin(), ascVals.end(), 0);
+  std::vector<int> V;
+  AdversaryComparator comp(N, V);
+  std::sort(ascVals.begin(), ascVals.end(), comp);
+  std::sort(V.begin(), V.end());
+  assert(std::is_sorted(V.begin(), V.end()));
+}
+
 int main(int, char**)
 {
     // test null range
@@ -171,6 +228,7 @@
     test_larger_sorts(1009);
 
     test_pointer_sort();
+    test_adversarial_quicksort(1 << 20);
 
-  return 0;
+    return 0;
 }