diff --git a/libcxx/docs/DesignDocs/DebugMode.rst b/libcxx/docs/DesignDocs/DebugMode.rst
--- a/libcxx/docs/DesignDocs/DebugMode.rst
+++ b/libcxx/docs/DesignDocs/DebugMode.rst
@@ -70,6 +70,12 @@
 
 The following checks are enabled by ``_LIBCPP_DEBUG``:
 
+  * Many algorithms, such as ``binary_search``, ``merge``, ``next_permutation``, and ``sort``,
+    wrap the user-provided comparator to assert that `!comp(y, x)` whenever
+    `comp(x, y)`. This can cause the user-provided comparator to be evaluated
+    up to twice as many times as it would be without ``_LIBCPP_DEBUG``, and
+    causes the library to violate some of the Standard's complexity clauses.
+
   * FIXME: Update this list
 
 Iterator Debugging Checks
diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
--- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge_comp.pass.cpp
@@ -6,8 +6,6 @@
 //
 //===----------------------------------------------------------------------===//
 
-// XFAIL: LIBCXX-DEBUG-FIXME
-
 // <algorithm>
 
 // template<BidirectionalIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
@@ -81,7 +79,9 @@
         assert(ia[0] == static_cast<int>(N)-1);
         assert(ia[N-1] == 0);
         assert(std::is_sorted(ia, ia+N, std::greater<value_type>()));
+#ifndef _LIBCPP_DEBUG
         assert(pred.count() <= (N-1));
+#endif
     }
     delete [] ia;
 }