Improve std::stable_sort using radix sort algorithm

[izvolov]

Summary

std::stable_sort uses a temporary buffer, which can be used to sort integers with radix sort algorithm. It dramatically improves the performance in case of sorting integers.

2021-10-23T13:05:54+03:00
Running ./projects/libcxx/benchmarks/algorithms.libcxx.out
Run on (12 X 2600 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x6)
  L1 Instruction 32 KiB (x6)
  L2 Unified 256 KiB (x6)
  L3 Unified 12288 KiB (x1)
Load Average: 3.27, 2.56, 2.18
--------------------------------------------------------------------------
Benchmark                                          Before            After 
--------------------------------------------------------------------------
BM_StableSort_uint32_Random_1                     3.43 ns          3.09 ns
BM_StableSort_uint32_Random_4                     4.97 ns          5.20 ns
BM_StableSort_uint32_Random_16                    8.87 ns          8.65 ns
BM_StableSort_uint32_Random_64                    13.9 ns          14.4 ns
BM_StableSort_uint32_Random_256                   22.1 ns          5.31 ns
BM_StableSort_uint32_Random_1024                  31.0 ns          3.97 ns
BM_StableSort_uint32_Random_16384                 47.7 ns          8.07 ns
BM_StableSort_uint32_Random_262144                66.5 ns          13.0 ns
BM_StableSort_uint32_Random_1048576               71.5 ns          20.8 ns
BM_StableSort_uint32_Random_33554432              95.4 ns          38.8 ns
BM_StableSort_uint32_Ascending_1                  3.71 ns          3.55 ns
BM_StableSort_uint32_Ascending_4                  1.43 ns          1.32 ns
BM_StableSort_uint32_Ascending_16                0.828 ns         0.963 ns
BM_StableSort_uint32_Ascending_64                0.637 ns         0.784 ns
BM_StableSort_uint32_Ascending_256                1.94 ns          4.52 ns
BM_StableSort_uint32_Ascending_1024               2.78 ns          2.56 ns
BM_StableSort_uint32_Ascending_16384              4.80 ns          1.91 ns
BM_StableSort_uint32_Ascending_262144             7.03 ns          2.77 ns
BM_StableSort_uint32_Ascending_1048576            9.50 ns          4.85 ns
BM_StableSort_uint32_Ascending_33554432           12.6 ns          8.25 ns
BM_StableSort_uint32_Descending_1                 3.67 ns          3.56 ns
BM_StableSort_uint32_Descending_4                 1.90 ns          2.19 ns
BM_StableSort_uint32_Descending_16                3.45 ns          5.12 ns
BM_StableSort_uint32_Descending_64                13.6 ns          18.9 ns
BM_StableSort_uint32_Descending_256               15.7 ns          5.26 ns
BM_StableSort_uint32_Descending_1024              15.9 ns          3.86 ns
BM_StableSort_uint32_Descending_16384             18.1 ns          9.01 ns
BM_StableSort_uint32_Descending_262144            20.5 ns          14.5 ns
BM_StableSort_uint32_Descending_1048576           21.8 ns          16.2 ns
BM_StableSort_uint32_Descending_33554432          39.7 ns          27.6 ns
BM_StableSort_uint32_SingleElement_1              3.68 ns          3.59 ns
BM_StableSort_uint32_SingleElement_4              1.41 ns          1.37 ns
BM_StableSort_uint32_SingleElement_16            0.822 ns         0.914 ns
BM_StableSort_uint32_SingleElement_64            0.632 ns         0.784 ns
BM_StableSort_uint32_SingleElement_256            1.94 ns          4.62 ns
BM_StableSort_uint32_SingleElement_1024           2.80 ns          2.76 ns
BM_StableSort_uint32_SingleElement_16384          4.81 ns          2.11 ns
BM_StableSort_uint32_SingleElement_262144         6.99 ns          2.95 ns
BM_StableSort_uint32_SingleElement_1048576        8.83 ns          5.49 ns
BM_StableSort_uint32_SingleElement_33554432       12.3 ns          8.51 ns
BM_StableSort_uint32_PipeOrgan_1                  3.65 ns          3.57 ns
BM_StableSort_uint32_PipeOrgan_4                  1.52 ns          1.57 ns
BM_StableSort_uint32_PipeOrgan_16                 1.86 ns          2.02 ns
BM_StableSort_uint32_PipeOrgan_64                 3.55 ns          5.08 ns
BM_StableSort_uint32_PipeOrgan_256                8.57 ns          5.26 ns
BM_StableSort_uint32_PipeOrgan_1024               9.38 ns          3.82 ns
BM_StableSort_uint32_PipeOrgan_16384              11.9 ns          9.58 ns
BM_StableSort_uint32_PipeOrgan_262144             13.8 ns          8.50 ns
BM_StableSort_uint32_PipeOrgan_1048576            15.4 ns          10.6 ns
BM_StableSort_uint32_PipeOrgan_33554432           25.5 ns          17.5 ns
BM_StableSort_uint64_Random_1                     3.27 ns          3.33 ns
BM_StableSort_uint64_Random_4                     5.31 ns          4.97 ns
BM_StableSort_uint64_Random_16                    8.97 ns          9.44 ns
BM_StableSort_uint64_Random_64                    14.6 ns          15.0 ns
BM_StableSort_uint64_Random_256                   23.2 ns          22.9 ns
BM_StableSort_uint64_Random_1024                  31.1 ns          7.06 ns
BM_StableSort_uint64_Random_16384                 47.2 ns          13.7 ns
BM_StableSort_uint64_Random_262144                63.9 ns          21.8 ns
BM_StableSort_uint64_Random_1048576               71.7 ns          19.7 ns
BM_StableSort_uint64_Random_33554432              97.1 ns          44.3 ns
BM_StableSort_uint64_Ascending_1                  3.34 ns          3.69 ns
BM_StableSort_uint64_Ascending_4                  1.54 ns          1.48 ns
BM_StableSort_uint64_Ascending_16                 1.00 ns         0.743 ns
BM_StableSort_uint64_Ascending_64                0.889 ns         0.605 ns
BM_StableSort_uint64_Ascending_256                2.00 ns          1.64 ns
BM_StableSort_uint64_Ascending_1024               2.71 ns          5.07 ns
BM_StableSort_uint64_Ascending_16384              4.44 ns          3.89 ns
BM_StableSort_uint64_Ascending_262144             7.39 ns          3.76 ns
BM_StableSort_uint64_Ascending_1048576            11.0 ns          7.27 ns
BM_StableSort_uint64_Ascending_33554432           15.3 ns          13.1 ns
BM_StableSort_uint64_Descending_1                 3.34 ns          3.70 ns
BM_StableSort_uint64_Descending_4                 2.04 ns          1.82 ns
BM_StableSort_uint64_Descending_16                4.21 ns          3.64 ns
BM_StableSort_uint64_Descending_64                16.2 ns          14.5 ns
BM_StableSort_uint64_Descending_256               17.7 ns          15.9 ns
BM_StableSort_uint64_Descending_1024              18.8 ns          7.12 ns
BM_StableSort_uint64_Descending_16384             20.3 ns          12.3 ns
BM_StableSort_uint64_Descending_262144            23.2 ns          27.9 ns
BM_StableSort_uint64_Descending_1048576           26.9 ns          31.1 ns
BM_StableSort_uint64_Descending_33554432          45.5 ns          36.6 ns
BM_StableSort_uint64_SingleElement_1              3.38 ns          3.87 ns
BM_StableSort_uint64_SingleElement_4              1.52 ns          1.45 ns
BM_StableSort_uint64_SingleElement_16             1.01 ns         0.744 ns
BM_StableSort_uint64_SingleElement_64            0.968 ns         0.619 ns
BM_StableSort_uint64_SingleElement_256            2.01 ns          1.64 ns
BM_StableSort_uint64_SingleElement_1024           2.70 ns          6.10 ns
BM_StableSort_uint64_SingleElement_16384          4.43 ns          5.07 ns
BM_StableSort_uint64_SingleElement_262144         6.94 ns          5.14 ns
BM_StableSort_uint64_SingleElement_1048576        10.8 ns          9.03 ns
BM_StableSort_uint64_SingleElement_33554432       15.4 ns          14.6 ns
BM_StableSort_uint64_PipeOrgan_1                  3.37 ns          3.67 ns
BM_StableSort_uint64_PipeOrgan_4                  1.71 ns          1.49 ns
BM_StableSort_uint64_PipeOrgan_16                 1.84 ns          1.74 ns
BM_StableSort_uint64_PipeOrgan_64                 4.99 ns          3.80 ns
BM_StableSort_uint64_PipeOrgan_256                10.6 ns          8.74 ns
BM_StableSort_uint64_PipeOrgan_1024               11.3 ns          7.29 ns
BM_StableSort_uint64_PipeOrgan_16384              12.8 ns          12.8 ns
BM_StableSort_uint64_PipeOrgan_262144             15.4 ns          28.2 ns
BM_StableSort_uint64_PipeOrgan_1048576            19.6 ns          20.4 ns
BM_StableSort_uint64_PipeOrgan_33554432           30.9 ns          25.2 ns

[izvolov]

Update formatting, include lost files.

[izvolov]

Update formatting.

[izvolov]

no comments

[izvolov]

C++17 only for now

[izvolov]

update

[izvolov]

defaultinit

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort_copy.h
   __algorithm/partial_sort.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/partition.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
+  __algorithm/radix_sort.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_copy.h
   __algorithm/remove_if.h
   __algorithm/remove.h
   __algorithm/replace_copy_if.h
   __algorithm/replace_copy.h
   __algorithm/replace_if.h
   __algorithm/replace.h

libcxx/include/__algorithm/radix_sort.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RADIX_SORT_H
+#define _LIBCPP___ALGORITHM_RADIX_SORT_H
+
+#include <__algorithm/copy.h>
+#include <__algorithm/for_each.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/move_iterator.h>
+#include <__utility/forward.h>
+#include <limits>
+#include <numeric>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+inline void __variadic_expansion_dummy(initializer_list<int>) {}
+
+#define EXPAND_VARIADIC(expression) __variadic_expansion_dummy({(expression, 0)...})
+
+template <typename _Iterator>
+constexpr auto __move_assign_please(_Iterator i)
+    -> enable_if_t<is_move_assignable<typename iterator_traits<_Iterator>::value_type>::value,
+                   move_iterator<_Iterator> > {
+  return make_move_iterator(move(i));
+}
+
+template <typename _Iterator>
+constexpr auto __move_assign_please(_Iterator i)
+    -> enable_if_t<not is_move_assignable<typename iterator_traits<_Iterator>::value_type>::value, _Iterator> {
+  return i;
+}
+
+template <typename _Integer>
+constexpr _Integer __intlog2_impl(_Integer integer) {
+  auto degree = _Integer{0};
+
+  while ((integer >>= 1) > 0) {
+    ++degree;
+  }
+
+  return degree;
+}
+
+template <typename _Integer>
+constexpr _Integer __intlog2(_Integer integer) {
+  static_assert(is_integral<_Integer>::value, "Must be an integral type");
+
+  return integer > 0 ? __intlog2_impl(integer)
+                     : throw domain_error("The binary logarithm is not defined on non-positive numbers");
+}
+
+template <typename _InputIterator, typename _OutputIterator>
+pair<_OutputIterator, typename iterator_traits<_InputIterator>::value_type>
+__partial_sum_max(_InputIterator first, _InputIterator last, _OutputIterator result) {
+  if (first == last)
+    return {result, 0};
+
+  auto max = *first;
+  typename iterator_traits<_InputIterator>::value_type sum = *first;
+  *result = sum;
+
+  while (++first != last) {
+    if (max < *first) {
+      max = *first;
+    }
+    sum = move(sum) + *first;
+    *++result = sum;
+  }
+  return {++result, max};
+}
+
+template <typename _Value, typename _Map, typename _Radix>
+struct __radix_sort_traits {
+  using image_type = decay_t<invoke_result_t<_Map, _Value> >;
+  static_assert(is_integral<image_type>::value, "");
+  static_assert(is_unsigned<image_type>::value, "");
+
+  using radix_type = decay_t<invoke_result_t<_Radix, image_type> >;
+  static_assert(is_integral<radix_type>::value, "");
+
+  constexpr static auto radix_value_range = numeric_limits<radix_type>::max() + 1;
+  constexpr static auto radix_size = __intlog2<uint64_t>(radix_value_range);
+  constexpr static auto radix_count = sizeof(image_type) * CHAR_BIT / radix_size;
+};
+
+template <typename _Value, typename _Map>
+struct __counting_sort_traits {
+  using image_type = decay_t<invoke_result_t<_Map, _Value> >;
+  static_assert(is_integral<image_type>::value, "");
+  static_assert(is_unsigned<image_type>::value, "");
+
+  constexpr static const auto value_range = numeric_limits<image_type>::max() + 1;
+  constexpr static auto radix_size = __intlog2<uint64_t>(value_range);
+};
+
+template <typename _Radix>
+auto __nth_radix(size_t radix_number, _Radix radix) {
+  return [radix_number, radix = move(radix)](auto n) {
+    using value_type = decltype(n);
+    static_assert(is_integral<value_type>::value, "");
+    static_assert(is_unsigned<value_type>::value, "");
+    using traits = __counting_sort_traits<value_type, _Radix>;
+
+    return radix(static_cast<value_type>(n >> traits::radix_size * radix_number));
+  };
+}
+
+template <typename _ForwardIterator, typename _Map, typename _Radix, typename _RandomAccessIterator1,
+          typename _RandomAccessIterator2, size_t... _Radices>
+bool __collect_impl(_ForwardIterator first, _ForwardIterator last, _Map map, _Radix radix,
+                    _RandomAccessIterator1 counters, _RandomAccessIterator2 maximums, index_sequence<_Radices...>) {
+  using value_type = typename iterator_traits<_ForwardIterator>::value_type;
+  constexpr auto radix_value_range = __radix_sort_traits<value_type, _Map, _Radix>::radix_value_range;
+
+  auto previous = numeric_limits<invoke_result_t<_Map, value_type> >::min();
+  auto is_sorted = true;
+  for_each(first, last, [&counters, &map, &radix, &previous, &is_sorted](const auto& value) {
+    auto current = map(value);
+    is_sorted &= (current >= previous);
+    previous = current;
+
+    EXPAND_VARIADIC(++counters[_Radices][__nth_radix(_Radices, radix)(current)]);
+  });
+
+  EXPAND_VARIADIC(
+      maximums[_Radices] =
+          __partial_sum_max(counters[_Radices], counters[_Radices] + radix_value_range, counters[_Radices]).second);
+
+  return is_sorted;
+}
+
+template <typename _ForwardIterator, typename _Map, typename _Radix, typename _RandomAccessIterator1,
+          typename _RandomAccessIterator2>
+bool __collect(_ForwardIterator first, _ForwardIterator last, _Map map, _Radix radix, _RandomAccessIterator1 counters,
+               _RandomAccessIterator2 maximums) {
+  using value_type = typename iterator_traits<_ForwardIterator>::value_type;
+  constexpr auto radix_count = __radix_sort_traits<value_type, _Map, _Radix>::radix_count;
+  return __collect_impl(first, last, map, radix, counters, maximums, make_index_sequence<radix_count>());
+}
+
+template <typename BidirectionalIterator, typename _RandomAccessIterator1, typename _Map,
+          typename _RandomAccessIterator2>
+void __dispose_backward(BidirectionalIterator first, BidirectionalIterator last, _RandomAccessIterator1 result,
+                        _Map map, _RandomAccessIterator2 counters) {
+  for_each(make_reverse_iterator(last), make_reverse_iterator(first), [&result, &counters, &map](auto&& preimage) {
+    auto index = --counters[map(preimage)];
+    result[index] = forward<decltype(preimage)>(preimage);
+  });
+}
+
+template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Map, typename _Radix>
+typename enable_if<
+    __radix_sort_traits<typename iterator_traits<_RandomAccessIterator1>::value_type, _Map, _Radix>::radix_count % 2 ==
+        0,
+    void>::type
+__radix_sort_impl(_RandomAccessIterator1 first, _RandomAccessIterator1 last, _RandomAccessIterator2 buffer_begin,
+                  _Map map, _Radix radix) {
+  using value_type = typename iterator_traits<_RandomAccessIterator1>::value_type;
+  using traits = __radix_sort_traits<value_type, _Map, _Radix>;
+
+  using difference_type = typename iterator_traits<_RandomAccessIterator1>::difference_type;
+  difference_type counters[traits::radix_count][traits::radix_value_range] = {{0}};
+  difference_type maximums[traits::radix_count] = {0};
+  const auto is_sorted = __collect(first, last, map, radix, counters, maximums);
+  if (not is_sorted) {
+    const auto range_size = distance(first, last);
+    auto buffer_end = buffer_begin + range_size;
+    for (size_t radix_number = 0; radix_number < traits::radix_count; radix_number += 2) {
+      const auto n0th_is_single = maximums[radix_number] == range_size;
+      const auto n1th_is_single = maximums[radix_number + 1] == range_size;
+
+      if (n0th_is_single && n1th_is_single) {
+        continue;
+      }
+
+      if (n0th_is_single) {
+        copy(__move_assign_please(first), __move_assign_please(last), buffer_begin);
+      } else {
+        auto n0th = [radix_number, &map, &radix](const auto& v) { return __nth_radix(radix_number, radix)(map(v)); };
+        __dispose_backward(__move_assign_please(first), __move_assign_please(last), buffer_begin, n0th,
+                           counters[radix_number]);
+      }
+
+      if (n1th_is_single) {
+        copy(__move_assign_please(buffer_begin), __move_assign_please(buffer_end), first);
+      } else {
+        auto n1th = [radix_number, &map, &radix](const auto& v) {
+          return __nth_radix(radix_number + 1, radix)(map(v));
+        };
+        __dispose_backward(__move_assign_please(buffer_begin), __move_assign_please(buffer_end), first, n1th,
+                           counters[radix_number + 1]);
+      }
+    }
+  }
+}
+
+constexpr auto __to_unsigned(bool b) { return b; }
+
+template <typename _Ip>
+constexpr auto __to_unsigned(_Ip n) {
+  constexpr const auto min_value = numeric_limits<_Ip>::min();
+  return static_cast<make_unsigned_t<_Ip> >(n ^ min_value);
+}
+
+struct __identity_fn {
+  template <typename _Tp>
+  constexpr decltype(auto) operator()(_Tp&& value) const {
+    return forward<_Tp>(value);
+  }
+};
+
+struct __low_byte_fn {
+  template <typename _Ip>
+  constexpr uint8_t operator()(_Ip integer) const {
+    static_assert(is_integral<_Ip>::value, "");
+    static_assert(is_unsigned<_Ip>::value, "");
+
+    return static_cast<uint8_t>(integer & 0xff);
+  }
+};
+
+template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Map, typename _Radix>
+void __radix_sort(_RandomAccessIterator1 first, _RandomAccessIterator1 last, _RandomAccessIterator2 buffer, _Map map,
+                  _Radix radix) {
+  auto map_to_unsigned = [map = move(map)](const auto& x) { return __to_unsigned(map(x)); };
+  __radix_sort_impl(first, last, buffer, map_to_unsigned, radix);
+}
+
+template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+void __radix_sort(_RandomAccessIterator1 first, _RandomAccessIterator1 last, _RandomAccessIterator2 buffer) {
+  __radix_sort(first, last, buffer, __identity_fn{}, __low_byte_fn{});
+}
+
+template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+bool __radix_sort(_RandomAccessIterator1 first, _RandomAccessIterator1 last, _RandomAccessIterator2 buffer,
+                  _BoolConstant<true>) {
+  __radix_sort(first, last, buffer, __identity_fn{}, __low_byte_fn{});
+  return true;
+}
+
+template <typename _RandomAccessIterator1, typename _RandomAccessIterator2>
+bool __radix_sort(_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _BoolConstant<false>) {
+  return false;
+}
+
+#undef EXPAND_VARIADIC
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_RADIX_SORT_H

libcxx/include/__algorithm/stable_sort.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_STABLE_SORT_H
 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
+#include <__algorithm/radix_sort.h>
 #include <__algorithm/sort.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 #include <memory>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
for (; __first1 != __last1; ++__result)
             *__result = _VSTD::move(*__first1);
             ++__first1;
         }
     }
     for (; __first2 != __last2; ++__first2, (void) ++__result)
         *__result = _VSTD::move(*__first2);
 }
 
-template <class _Compare, class _RandomAccessIterator>
-void
-__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+template <class _Compare, class _RandomAccessIterator, bool __EnableRadixSort>
+void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
-              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);
+                   typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size,
+                   _BoolConstant<__EnableRadixSort>);
 
-template <class _Compare, class _RandomAccessIterator>
-void
-__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
+template <class _Compare, class _RandomAccessIterator, bool __EnableRadixSort>
+void __stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp,
                         typename iterator_traits<_RandomAccessIterator>::difference_type __len,
-                   typename iterator_traits<_RandomAccessIterator>::value_type* __first2)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    switch (__len)
-    {
-    case 0:
-        return;
-    case 1:
-        ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
-        return;
-    case 2:
-        __destruct_n __d(0);
-        unique_ptr<value_type, __destruct_n&> __h2(__first2, __d);
-        if (__comp(*--__last1, *__first1))
-        {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
-            __d.template __incr<value_type>();
-            ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
-        }
-        else
-        {
-            ::new ((void*)__first2) value_type(_VSTD::move(*__first1));
-            __d.template __incr<value_type>();
-            ++__first2;
-            ::new ((void*)__first2) value_type(_VSTD::move(*__last1));
-        }
-        __h2.release();
-        return;
-    }
-    if (__len <= 8)
-    {
-        _VSTD::__insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp);
-        return;
-    }
-    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
-    _RandomAccessIterator __m = __first1 + __l2;
-    _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2);
-    _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2);
-    _VSTD::__merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);
+                        typename iterator_traits<_RandomAccessIterator>::value_type* __first2,
+                        _BoolConstant<__EnableRadixSort> __rs) {
+  switch (__len) {
+    if (__comp(*--__last1, *__first1)) {
+    } else {
+  if (__len <= 8) {
+  _VSTD::__stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2, __rs);
+  _VSTD::__stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2, __rs);
 }
 
 template <class _Tp>
 struct __stable_sort_switch
 {
     static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;
 };
 
-template <class _Compare, class _RandomAccessIterator>
-void
-__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+template <class _Tp>
+struct __radix_sort_min_switch {
+  static const unsigned value = (1 << 6) * sizeof(_Tp);
+};
+
+template <class _Tp>
+struct __radix_sort_max_switch {
+  static const unsigned value = (1 << 15) * sizeof(_Tp);
+};
+
+template <class _Compare, class _RandomAccessIterator, bool __EnableRadixSort>
+void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
                    typename iterator_traits<_RandomAccessIterator>::difference_type __len,
-              typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    switch (__len)
-    {
-    case 0:
-    case 1:
-        return;
-    case 2:
-        if (__comp(*--__last, *__first))
-            swap(*__first, *__last);
-        return;
-    }
-    if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value))
-    {
-        _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
-        return;
-    }
-    typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2;
-    _RandomAccessIterator __m = __first + __l2;
-    if (__len <= __buff_size)
-    {
-        __destruct_n __d(0);
-        unique_ptr<value_type, __destruct_n&> __h2(__buff, __d);
-        _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
-        __d.__set(__l2, (value_type*)nullptr);
-        _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2);
-        __d.__set(__len, (value_type*)nullptr);
-        _VSTD::__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
+                   typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size,
+                   _BoolConstant<__EnableRadixSort> __rs) {
+  switch (__len) {
+  if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
+  if (__len <= __buff_size && __len >= __radix_sort_min_switch<value_type>::value &&
+      __len <= __radix_sort_max_switch<value_type>::value) {
+    if (_VSTD::__radix_sort(__first, __last, __buff, __rs)) {
+      return;
+    }
+  }
+  if (__len <= __buff_size) {
+    _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff, __rs);
+    _VSTD::__stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2, __rs);
     //         _VSTD::__merge<_Compare>(move_iterator<value_type*>(__buff),
     //                                  move_iterator<value_type*>(__buff + __l2),
     //                                  move_iterator<_RandomAccessIterator>(__buff + __l2),
     //                                  move_iterator<_RandomAccessIterator>(__buff + __len),
     //                                  __first, __comp);
-        return;
-    }
-    _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
-    _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size);
-    _VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
+  _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size, __rs);
+  _VSTD::__stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size, __rs);
 }
 
-template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    difference_type __len = __last - __first;
-    pair<value_type*, ptrdiff_t> __buf(0, 0);
-    unique_ptr<value_type, __return_temporary_buffer> __h;
-    if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value))
-    {
-        __buf = _VSTD::get_temporary_buffer<value_type>(__len);
-        __h.reset(__buf.first);
-    }
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
+template <class _RandomAccessIterator, class _Compare, bool __EnableRadixSort>
+inline _LIBCPP_INLINE_VISIBILITY void __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+                                                    _Compare __comp, _BoolConstant<__EnableRadixSort> __rs) {
+  if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) {
+  _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second, __rs);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_INLINE_VISIBILITY void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
+                                                  _Compare __comp) {
+  _VSTD::__stable_sort(__first, __last, __comp, _BoolConstant<false>{});
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
-    _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
+  _VSTD::__stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>(),
+                       _BoolConstant<is_integral<value_type>::value>{});
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/radix_sort.module.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__algorithm/radix_sort.h'}}
+#include <__algorithm/radix_sort.h>