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 O(n log n) worst-case time complexity.
int[] array = [ 1, 2, 3, 4 ]; // sort in descending order array.sort!("a > b"); assert(array == [ 4, 3, 2, 1 ]); // sort in ascending order array.sort(); assert(array == [ 1, 2, 3, 4 ]); // sort with reusable comparator and chain alias myComp = (x, y) => x > y; assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
// Showcase stable sorting import std.algorithm.mutation : SwapStrategy; string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ]; sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words); assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
// 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));
Sorts a random-access range according to the predicate less.
Performs O(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.