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.
`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`. The left-hand side of the range `lhs` is assumed to be already sorted; `rhs` is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of `lhs` and `rhs`. Performs Ο(`lhs.length + rhs.length * log(rhs.length)`) (best case) to Ο(`(lhs.length + rhs.length) * log(lhs.length + rhs.length)`) (worst-case) evaluations of `swap`.
`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`. The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sorting-based solution because it needs space for the index in addition to the original collection. The complexity is the same as `sort`'s.
`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. 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`.
`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. The algorithm has a constant runtime complexity with respect to the number of permutations created. Due to the number of unique values of `ulong` only the first 21 elements of `range` can be permuted. The rest of the range will therefore not be permuted. This algorithm uses the Lehmer Code.
`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. Performs Ο(`r.length * log(mid)`) evaluations of `pred`. The implementation simply calls `topN!(less, ss)(r, n)` and then `sort!(less, ss)(r[0 .. n])`.
`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`. Specifically, reorders the range `r = [left, rightclass="pln">RPAREN` using `swap` such that all elements `i` for which `predicate(i)` is `true` come before all elements `j` for which `predicate(j)` returns `false`.
`partition3(r, pivot)`	Rearranges elements in `r` in three adjacent ranges and returns them. The first and leftmost range only contains elements in `r` less than `pivot`. The second and middle range only contains elements in `r` that are equal to `pivot`. Finally, the third and rightmost range only contains elements in `r` that are greater than `pivot`. The less-than test is defined by the binary function `less`.
`pivotPartition(r, pivot)`	Partitions `r` around `pivot` using comparison function `less`, algorithm akin to Hoare partition. Specifically, permutes elements of `r` and returns an index `k < r.length` such that:
`schwartzSort(r)`	Alternative sorting method that should be used when comparing keys involves an expensive computation. Instead of using `less(a, b)` for comparing elements, `schwartzSort` uses `less(transform(a), transform(b))`. The values of the `transform` function are precomputed in a temporary array, thus saving on repeatedly computing it. Conversely, if the cost of `transform` is small compared to the cost of allocating and filling the precomputed array, `sort` may be faster and therefore preferable.
`sort(r)`	Sorts a random-access range according to the predicate `less`. Performs Ο(`r.length * log(r.length)`) evaluations of `less`. If `less` involves expensive computations on the sort key, it may be worthwhile to use `schwartzSort` instead.
`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. In addition, it also partitions `r` such that all elements `e1` from `r[0]` to `r[nth]` satisfy `!less(r[nth], e1)`, and all elements `e2` from `r[nth]` to `r[r.length]` satisfy `!less(e2, r[nth])`. Effectively, it finds the nth smallest (according to `less`) elements in `r`. Performs an expected Ο(`r.length`) (if unstable) or Ο(`r.length * log(r.length)`) (if stable) evaluations of `less` and `swap`.
`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`. Elements of `source` are not touched. If `sorted` is `true`, the target is sorted. Otherwise, the target respects the heap property.
`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. The call `multiSort!("a.id < b.id", "a.date > b.date")(r)` sorts the range `r` by `id` ascending, and sorts elements that have the same `id` by `date` descending. Such a call is equivalent to `sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r)`, but `multiSort` is faster because it does fewer comparisons (in addition to being more convenient).

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.