How do I sort a subrange of a range `x` where the subrange is
defined by a lower and upper (in this case exlusive) element
contained within `x`?
auto x = [1,2,7,4,2,6,8,3,9,3];
auto y = sortSubRange(x, 3,5];
should yield `y` being
[3,3,4]
and `x` being
[a ,3,3,4, b]
where
- a contains the elements 1,2,2 in some undefined order and
- b contains the elements 6,7,8,9 in some undefined order
.
Algorithm was highlighted in C++ at
https://www.youtube.com/watch?v=0WlJEz2wb8Y&t=1719s
as
/** Sort sub-range [sub_begin, sub_end] of [begin, end].
*
* Describe at https://www.youtube.com/watch?v=0WlJEz2wb8Y&t=2686s
*/
template <typename I> // I models RandomAccessIterator
void sort_subrange(I begin, I end,
I sub_begin, I sub_end)
{
if (sub_begin == sub_end) { return; }
if (sub_begin != begin)
{
std::nth_element(begin, sub_begin, end);
++sub_begin;
}
std::partial_sort(sub_begin, sub_begin, end);
}
