SortedRange!(Range, less) sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range 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
Stable sorting requires hasAssignableElements!Range to be true.
sort returns a 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 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 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 cmp instead.
less | The predicate to sort by. |
ss | The swapping strategy to use. |
r | The range to sort. |
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.