36#ifndef RANGES_V3_ALGORITHM_STABLE_SORT_HPP
37#define RANGES_V3_ALGORITHM_STABLE_SORT_HPP
60#include <range/v3/utility/static_const.hpp>
62#include <range/v3/detail/prologue.hpp>
72 template<
typename I,
typename C,
typename P>
73 void inplace_stable_sort(I first, I last, C & pred, P & proj)
76 return detail::insertion_sort(first, last, pred, proj), void();
78 detail::inplace_stable_sort(first, middle, pred, proj);
79 detail::inplace_stable_sort(middle, last, pred, proj);
80 detail::inplace_merge_no_buffer(first,
89 template<
typename I1,
typename I2,
typename D,
typename C,
typename P>
90 void merge_sort_loop(I1 first, I1 last, I2 result, D step_size, C & pred,
93 D two_step = 2 * step_size;
94 while(last - first >= two_step)
96 result = merge(make_move_iterator(first),
97 make_move_iterator(first + step_size),
98 make_move_iterator(first + step_size),
99 make_move_iterator(first + two_step),
107 step_size = ranges::min(D(last - first), step_size);
108 merge(make_move_iterator(first),
109 make_move_iterator(first + step_size),
110 make_move_iterator(first + step_size),
111 make_move_iterator(last),
118 constexpr int merge_sort_chunk_size()
123 template<
typename I,
typename D,
typename C,
typename P>
124 void chunk_insertion_sort(I first, I last, D chunk_size, C & pred, P & proj)
126 while(last - first >= chunk_size)
128 detail::insertion_sort(first, first + chunk_size, pred, proj);
131 detail::insertion_sort(first, last, pred, proj);
136 template<
typename I,
typename V,
typename C,
typename P>
137 void merge_sort_with_buffer(I first, I last, V * buffer, C & pred, P & proj)
139 iter_difference_t<I> len = last -
first,
140 step_size = detail::merge_sort_chunk_size();
141 detail::chunk_insertion_sort(first, last, step_size, pred, proj);
146 V * buffer_end = buffer +
static_cast<std::ptrdiff_t
>(len);
147 auto tmpbuf = make_raw_buffer(buffer);
148 detail::merge_sort_loop(first, last, tmpbuf.begin(), step_size, pred, proj);
151 detail::merge_sort_loop(
152 buffer, buffer_end, first, (std::ptrdiff_t)step_size, pred, proj);
156 detail::merge_sort_loop(first, last, buffer, step_size, pred, proj);
162 template<
typename I,
typename V,
typename C,
typename P>
163 void stable_sort_adaptive(I first, I last, V * buffer, std::ptrdiff_t buffer_size,
166 iter_difference_t<I> len = (last -
first + 1) / 2;
167 I middle =
first + len;
168 if(len > buffer_size)
170 detail::stable_sort_adaptive(
171 first, middle, buffer, buffer_size, pred, proj);
172 detail::stable_sort_adaptive(
173 middle, last, buffer, buffer_size, pred, proj);
177 detail::merge_sort_with_buffer(first, middle, buffer, pred, proj);
178 detail::merge_sort_with_buffer(middle, last, buffer, pred, proj);
180 detail::merge_adaptive(first,
193 RANGES_FUNC_BEGIN(stable_sort)
196 template(
typename I,
typename S,
typename C =
less,
typename P = identity)(
197 requires sortable<I, C, P> AND random_access_iterator<I> AND
199 I RANGES_FUNC(stable_sort)(I
first, S end_, C pred = C{}, P proj = P{})
201 I last = ranges::next(first, end_);
202 using D = iter_difference_t<I>;
203 using V = iter_value_t<I>;
204 D len = last -
first;
206 len > 256 ? detail::get_temporary_buffer<V>(len) : detail::value_init{};
207 std::unique_ptr<V, detail::return_temporary_buffer> h{buf.first};
208 if(buf.first ==
nullptr)
209 detail::inplace_stable_sort(first, last, pred, proj);
211 detail::stable_sort_adaptive(
212 first, last, buf.first, buf.second, pred, proj);
217 template(
typename Rng,
typename C =
less,
typename P = identity)(
218 requires sortable<iterator_t<Rng>, C, P> AND random_access_range<Rng>)
219 borrowed_iterator_t<Rng>
220 RANGES_FUNC(stable_sort)(Rng && rng, C pred = C{}, P proj = P{})
222 return (*
this)(begin(rng), end(rng), std::move(pred), std::move(proj));
225 RANGES_FUNC_END(stable_sort)
229 using ranges::stable_sort;
234#include <range/v3/detail/epilogue.hpp>
front< Pair > first
Retrieve the first element of the pair Pair.
Definition meta.hpp:2251
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition meta.hpp:255