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.

# Module `std.algorithm.sorting`

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

Cheat Sheet
Function Name Description
`completeSort` If `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 `class="pln">REF chain, std,range(a, b)` is sorted.
`isPartitioned` `isPartitioned!"a < 0"([-1, -2, 1, 0, 2])` returns `true` because the predicate is `true` for a portion of the range and `false` afterwards.
`isSorted` `isSorted([1, 1, 2, 3])` returns `true`.
`isStrictlyMonotonic` `isStrictlyMonotonic([1, 1, 2, 3])` returns `false`.
`ordered` `ordered(1, 1, 2, 3)` returns `true`.
`strictlyOrdered` `strictlyOrdered(1, 1, 2, 3)` returns `false`.
`makeIndex` Creates a separate index for a range.
`merge` Lazily merges two or more sorted ranges.
`multiSort` Sorts by multiple keys.
`nextEvenPermutation` Computes the next lexicographically greater even permutation of a range in-place.
`nextPermutation` Computes the next lexicographically greater permutation of a range in-place.
`nthPermutation` Computes the nth permutation of a range in-place.
`partialSort` If `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.
`partition` Partitions a range according to a unary predicate.
`partition3` Partitions 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.
`pivotPartition` Partitions 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.
`schwartzSort` Sorts with the help of the Schwartzian transform.
`sort` Sorts.
`topN` Separates the top elements in a range, akin to Quickselect.
`topNCopy` Copies out the top elements of a range.
`topNIndex` Builds an index of the top elements of a range.

## Functions

NameDescription
``` completeSort(lhs, rhs) ``` Sorts the random-access range `chain(lhs, rhs)` according to predicate `less`.
``` isPartitioned(r) ```
``` isSorted(r) ``` Checks whether a forward range is sorted according to the comparison operation `less`. Performs Ο(`r.length`) evaluations of `less`.
``` isStrictlyMonotonic(r) ``` Checks whether a forward range is sorted according to the comparison operation `less`. Performs Ο(`r.length`) evaluations of `less`.
``` makeIndex(r, index) ``` Computes an index for `r` based on the comparison `less`.
``` merge(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(range) ``` Permutes `range` in-place to the next lexicographically greater even permutation.
``` nextPermutation(range) ``` Permutes `range` in-place to the next lexicographically greater permutation.
``` nthPermutation(range, perm) ``` Permutes `range` into the `perm` permutation.
``` nthPermutationImpl(range, perm) ```
``` ordered(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(r, 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(r1, r2) ``` Stores the smallest elements of the two ranges in the left-hand range in sorted order.
``` partition(r) ``` Partitions a range in two using the given `predicate`.
``` partition3(r, pivot) ``` Rearranges elements in `r` in three adjacent ranges and returns them.
``` pivotPartition(r, pivot) ``` Partitions `r` around `pivot` using comparison function `less`, algorithm akin to Hoare partition.
``` schwartzSort(r) ``` Alternative sorting method that should be used when comparing keys involves an expensive computation.
``` sort(r) ``` Sorts a random-access range according to the predicate `less`.
``` strictlyOrdered(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(r, 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(r1, r2) ``` Stores the smallest elements of the two ranges in the left-hand range.
``` topNCopy(source, target, sorted) ``` Copies the top `n` elements of the input range `source` into the random-access range `target`, where `n = target.length`.
``` topNIndex(r, index, 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

NameDescription
``` multiSort ``` Sorts a range by multiple keys.

## Aliases

NameTypeDescription
`SortOutput` `Flag!("sortOutput")` Specifies whether the output of certain algorithm is desired in sorted format.