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

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
}

On Friday, 16 November 2018 at 12:08:33 UTC, Stanislav Blinov wrote:
> 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];
> }

Wonderful!