Re: Sorting a subrange

[Stanislav Blinov via Digitalmars-d-learn]

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
}