Index: cmake/modules/HandleLLVMOptions.cmake
===================================================================
--- cmake/modules/HandleLLVMOptions.cmake
+++ cmake/modules/HandleLLVMOptions.cmake
@@ -105,6 +105,10 @@
   set( LLVM_ENABLE_REVERSE_ITERATION 1 )
 endif()
 
+if( LLVM_SHUFFLE_BEFORE_SORT )
+  set( LLVM_ENABLE_SHUFFLE_BEFORE_SORT 1 )
+endif()
+
 if(WIN32)
   set(LLVM_HAVE_LINK_VERSION_SCRIPT 0)
   if(CYGWIN)
Index: include/llvm/ADT/STLExtras.h
===================================================================
--- include/llvm/ADT/STLExtras.h
+++ include/llvm/ADT/STLExtras.h
@@ -32,6 +32,7 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"
+#include "llvm/Config/abi-breaking.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 
@@ -771,6 +772,9 @@
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#if LLVM_ENABLE_SHUFFLE_BEFORE_SORT
+  std::random_shuffle(Start, End);
+#endif
   qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
 }
 
@@ -784,10 +788,30 @@
   // behavior with an empty sequence.
   auto NElts = End - Start;
   if (NElts <= 1) return;
+#if LLVM_ENABLE_SHUFFLE_BEFORE_SORT
+  std::random_shuffle(Start, End);
+#endif
   qsort(&*Start, NElts, sizeof(*Start),
         reinterpret_cast<int (*)(const void *, const void *)>(Compare));
 }
 
+// Provide wrappers to std::sort which shuffle the elements before sorting.
+template <typename IteratorTy>
+void sort(IteratorTy Start, IteratorTy End) {
+#if LLVM_ENABLE_SHUFFLE_BEFORE_SORT
+  std::random_shuffle(Start, End);
+#endif
+  std::sort(Start, End);
+}
+
+template <typename IteratorTy, typename Compare>
+void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
+#if LLVM_ENABLE_SHUFFLE_BEFORE_SORT
+  std::random_shuffle(Start, End);
+#endif
+  std::sort(Start, End, Comp);
+}
+
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
Index: include/llvm/Config/abi-breaking.h.cmake
===================================================================
--- include/llvm/Config/abi-breaking.h.cmake
+++ include/llvm/Config/abi-breaking.h.cmake
@@ -18,6 +18,9 @@
 /* Define to enable reverse iteration of unordered llvm containers */
 #cmakedefine01 LLVM_ENABLE_REVERSE_ITERATION
 
+/* Define to enable shuffling of elements before sorting */
+#cmakedefine01 LLVM_ENABLE_SHUFFLE_BEFORE_SORT
+
 /* Allow selectively disabling link-time mismatch checking so that header-only
    ADT content from LLVM can be used without linking libSupport. */
 #if !LLVM_DISABLE_ABI_BREAKING_CHECKS_ENFORCING