Search
View source code
Display the source code in std/algorithm/sorting.d from which this page was generated on github.
Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# Function `std.algorithm.sorting.merge`

Merge multiple sorted ranges `rs` with less-than predicate function `pred` into one single sorted output range containing the sorted union of the elements of inputs. Duplicates are not eliminated, meaning that the total number of elements in the output is the sum of all elements in the ranges passed to it; the `length` member is offered if all inputs also have `length`. The element types of all the inputs must have a common type `CommonType`.

``` Merge!(less,Rs) merge(alias less, Rs...) (   Rs rs ) if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) && !is(CommonType!(staticMap!(ElementType, Rs)) == void)); ```

## Parameters

NameDescription
less Predicate the given ranges are sorted by.
rs The ranges to compute the union for.

## Returns

A range containing the union of the given ranges.

## Details

All of its inputs are assumed to be sorted. This can mean that inputs are instances of `std.range.SortedRange`. Use the result of ` sort`, or `std.range.assumeSorted` to merge ranges known to be sorted (show in the example below). Note that there is currently no way of ensuring that two or more instances of ` std.range.SortedRange` are sorted using a specific comparison function `pred`. Therefore no checking is done here to assure that all inputs `rs` are instances of `std.range.SortedRange`.

This algorithm is lazy, doing work progressively as elements are pulled off the result.

Time complexity is proportional to the sum of element counts over all inputs.

If all inputs have the same element type and offer it by `ref`, output becomes a range with mutable `front` (and `back` where appropriate) that reflects in the original inputs.

If any of the inputs `rs` is infinite so is the result (`empty` being always `false`).

`multiwayMerge` for an analogous function that merges a dynamic number of ranges.

## Example

``````import std.algorithm.comparison : equal;
import std.range : retro;

int[] a = [1, 3, 5];
int[] b = [2, 3, 4];

assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
``````

## Example

test bi-directional access and common type

``````import std.algorithm.comparison : equal;
import std.range : retro;
import std.traits : CommonType;

alias S = short;
alias I = int;
alias D = double;

S[] a = [1, 2, 3];
I[] b = [50, 60];
D[] c = [10, 20, 30, 40];

auto m = merge(a, b, c);

static assert(is(typeof(m.front) == CommonType!(S, I, D)));

assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60]));
assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1]));

m.popFront();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60]));
m.popBack();
assert(equal(m, [2, 3, 10, 20, 30, 40, 50]));
m.popFront();
assert(equal(m, [3, 10, 20, 30, 40, 50]));
m.popBack();
assert(equal(m, [3, 10, 20, 30, 40]));
m.popFront();
assert(equal(m, [10, 20, 30, 40]));
m.popBack();
assert(equal(m, [10, 20, 30]));
m.popFront();
assert(equal(m, [20, 30]));
m.popBack();
assert(equal(m, ));
m.popFront();
assert(m.empty);
``````