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.sort`

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

``` SortedRange!(Range,less) sort(alias less, SwapStrategy ss = SwapStrategy.unstable, Range) (   Range r ); ```

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.

Stable sorting requires `hasAssignableElements!Range` to be true.

`sort` returns a `std.range.SortedRange` over the original range, allowing functions that can take advantage of sorted data to know that the range is sorted and adjust accordingly. The `std.range.SortedRange` is a wrapper around the original range, so both it and the original range are sorted. Other functions can't know that the original range has been sorted, but they can know that `std.range.SortedRange` has been sorted.

## Preconditions

The predicate is expected to satisfy certain rules in order for `sort` to behave as expected - otherwise, the program may fail on certain inputs (but not others) when not compiled in release mode, due to the cursory `assumeSorted` check. Specifically, `sort` expects `less(a,b) && less(b,c)` to imply `less(a,c)` (transitivity), and, conversely, `!less(a,b) && !less(b,c)` to imply `!less(a,c)`. Note that the default predicate (`"a < b"`) does not always satisfy these conditions for floating point types, because the expression will always be `false` when either `a` or `b` is NaN. Use `std.math.cmp` instead.

## Parameters

NameDescription
less The predicate to sort by.
ss The swapping strategy to use.
r The range to sort.

## Returns

The initial range wrapped as a `SortedRange` with the predicate `binaryFun!less`.

## Algorithms

Introsort is used for unstable sorting and Timsort is used for stable sorting. Each algorithm has benefits beyond stability. Introsort is generally faster but Timsort may achieve greater speeds on data with low entropy or if predicate calls are expensive. Introsort performs no allocations whereas Timsort will perform one or more allocations per call. Both algorithms have Ο(`n log n`) worst-case time complexity.

`std.range.assumeSorted`
`std.range.SortedRange`
`SwapStrategy`
`binaryFun`

## Example

``````int[] array = [ 1, 2, 3, 4 ];

// sort in descending order
array.sort!("a > b");
writeln(array); // [4, 3, 2, 1]

// sort in ascending order
array.sort();
writeln(array); // [1, 2, 3, 4]

// sort with reusable comparator and chain
alias myComp = (x, y) => x > y;
writeln(array.sort!(myComp).release); // [4, 3, 2, 1]
``````

## Example

``````// Showcase stable sorting
import std.algorithm.mutation : SwapStrategy;
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
writeln(words); // ["a", "aBc", "abc", "ABC", "b", "c"]
``````

## Example

``````// Sorting floating-point numbers in presence of NaN
double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];

import std.algorithm.comparison : equal;
import std.math.operations : cmp;
import std.math.traits : isIdentical;

sort!((a, b) => cmp(a, b) < 0)(numbers);

double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
assert(numbers.equal!isIdentical(sorted));
``````