Display the source code in std/algorithm/sorting.d from which this page was generated on github.

If you spot a problem with this page, click here to create a Bugzilla issue.

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

Name	Description
`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

Name	Description
`multiSort`	Sorts a range by multiple keys.

Aliases

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

Authors

Andrei Alexandrescu

License

Boost License 1.0.