std.algorithm.sorting

This is a submodule of std.algorithm. It contains generic sorting algorithms.

Cheat Sheet
Function NameDescription
completeSortIf a = [10, 20, 30] and b = [40, 6, 15], then completeSort(a, b) leaves a = [6, 10, 15] and b = [20, 30, 40]. The range a must be sorted prior to the call, and as a result the combination $(REF chain, std,range)(a, b) is sorted.
isPartitionedisPartitioned!"a < 0"([-1, -2, 1, 0, 2]) returns true because the predicate is true for a portion of the range and false afterwards.
isSortedisSorted([1, 1, 2, 3]) returns true.
isStrictlyMonotonicisStrictlyMonotonic([1, 1, 2, 3]) returns false.
orderedordered(1, 1, 2, 3) returns true.
strictlyOrderedstrictlyOrdered(1, 1, 2, 3) returns false.
makeIndexCreates a separate index for a range.
mergeLazily merges two or more sorted ranges.
multiSortSorts by multiple keys.
nextEvenPermutationComputes the next lexicographically greater even permutation of a range in-place.
nextPermutationComputes the next lexicographically greater permutation of a range in-place.
nthPermutationComputes the nth permutation of a range in-place.
partialSortIf a = [5, 4, 3, 2, 1], then partialSort(a, 3) leaves a[0 .. 3] = [1, 2, 3]. The other elements of a are left in an unspecified order.
partitionPartitions a range according to a unary predicate.
partition3Partitions a range according to a binary predicate in three parts (less than, equal, greater than the given pivot). Pivot is not given as an index, but instead as an element independent from the range's content.
pivotPartitionPartitions a range according to a binary predicate in two parts: less than or equal, and greater than or equal to the given pivot, passed as an index in the range.
schwartzSortSorts with the help of the Schwartzian transform.
sortSorts.
topNSeparates the top elements in a range, akin to Quickselect.
topNCopyCopies out the top elements of a range.
topNIndexBuilds an index of the top elements of a range.

Members

Aliases

SortOutput
alias SortOutput = Flag!"sortOutput"

Specifies whether the output of certain algorithm is desired in sorted format.

Functions

completeSort
void completeSort(SortedRange!(Lhs, less) lhs, Rhs rhs)

Sorts the random-access range chain(lhs, rhs) according to predicate less.

isPartitioned
bool isPartitioned(Range r)
isSorted
bool isSorted(Range r)
isStrictlyMonotonic
bool isStrictlyMonotonic(Range r)

Checks whether a forward range is sorted according to the comparison operation less. Performs O(r.length) evaluations of less.

makeIndex
SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b)) makeIndex(Range r, RangeIndex index)
void makeIndex(Range r, RangeIndex index)

Computes an index for r based on the comparison less.

merge
Merge!(less, Rs) merge(Rs rs)

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.

nextEvenPermutation
bool nextEvenPermutation(BidirectionalRange range)

Permutes range in-place to the next lexicographically greater even permutation.

nextPermutation
bool nextPermutation(BidirectionalRange range)

Permutes range in-place to the next lexicographically greater permutation.

nthPermutation
Range nthPermutation(Range range, ulong perm)

Permutes range into the perm permutation.

nthPermutationImpl
bool nthPermutationImpl(Range range, ulong perm)
ordered
bool ordered(T values)

Like isSorted, returns true if the given values are ordered according to the comparison operation less. Unlike isSorted, takes values directly instead of structured in a range.

partialSort
void partialSort(Range r, size_t n)

Reorders the random-access range r such that the range r[0 .. mid] is the same as if the entire r were sorted, and leaves the range r[mid .. r.length] in no particular order.

partialSort
void partialSort(Range1 r1, Range2 r2)

Stores the smallest elements of the two ranges in the left-hand range in sorted order.

partition
Range partition(Range r)

Partitions a range in two using the given predicate.

partition3
auto partition3(Range r, E pivot)

Rearranges elements in r in three adjacent ranges and returns them.

pivotPartition
size_t pivotPartition(Range r, size_t pivot)

Partitions r around pivot using comparison function less, algorithm akin to Hoare partition.

schwartzSort
SortedRange!(R, ((a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b)))) schwartzSort(R r)
auto schwartzSort(R r)

Alternative sorting method that should be used when comparing keys involves an expensive computation.

sort
SortedRange!(Range, less) sort(Range r)

Sorts a random-access range according to the predicate less.

strictlyOrdered
bool strictlyOrdered(T values)

Like isSorted, returns true if the given values are ordered according to the comparison operation less. Unlike isSorted, takes values directly instead of structured in a range.

topN
auto topN(Range r, size_t nth)

Reorders the range r using swap such that r[nth] refers to the element that would fall there if the range were fully sorted.

topN
auto topN(Range1 r1, Range2 r2)

Stores the smallest elements of the two ranges in the left-hand range.

topNCopy
TRange topNCopy(SRange source, TRange target, SortOutput sorted)

Copies the top n elements of the input range source into the random-access range target, where n = target.length.

topNIndex
void topNIndex(Range r, RangeIndex index, SortOutput sorted)

Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).

Templates

multiSort
template multiSort(less...)

Sorts a range by multiple keys.

Meta