Sorting a subrange

[Stanislav Blinov]

On Friday, 16 November 2018 at 11:24:20 UTC, Per Nordlöw wrote:

> /** 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);
> }

Back-of-the-envelope translation (probably some error checking 
would be in order):

import std.range.primitives : isRandomAccessRange;

auto sortSubRange(R)(R range, size_t i, size_t j) if 
(isRandomAccessRange!R) {
     import std.algorithm.sorting : topN, partialSort;
     size_t start = i;
     if (i != 0) {
         topN(range, i);
         start++;
     }
     partialSort(range[start .. $], j-start);
     return range[i .. j];
}

void main() {
     auto x = [1,2,7,4,2,6,8,3,9,3];
     auto y = sortSubRange(x, 3, 6);
     import std.stdio;
     writeln(y); // 3, 3, 4
     writeln(x); // ex. 2, 2, 1, 3, 3, 4, 6, 7, 9, 8
}