This switches the standard library's sort algorithm from an in-place
introsort to use a modified timsort, a stable, adaptive sort that
merges runs using a temporary buffer. This implementation performs
straight merges instead of adopting timsort's galloping strategy.
In addition to maintaining the relative order of equal/non-comparable
elements, this algorithm outperforms the introsort on data with any
intrinsic structure, such as runs of ascending or descending elements
or a significant number of equality collisions.
* Replace bodies of Comparable versions with calls to sort(by:)
* Make _insertionSort a method
* Make _sort3 a method
* Make _partition a method
* Make _introSort a method
* Make _siftDown, _heapify, _heapsort methods
* Other minor cleanup
SwiftPrivate/PRNG.swift:
- currently uses `theGlobalMT19937`;
- previously used `arc4random` (see #1939);
- is obsoleted by SE-0202: Random Unification.
* Make Range conditionally a Collection
* Convert ClosedRange to conditionally a collection
* De-gyb Range/ClosedRange, refactoring some methods.
* Remove use of Countable{Closed}Range from stdlib
* Remove Countable use from Foundation
* Fix test errors and warnings resulting from Range/CountableRange collapse
* fix prespecialize test for new mangling
* Update CoreAudio use of CountableRange
* Update SwiftSyntax use of CountableRange
* Restore ClosedRange.Index: Hashable conformance
* Move fixed typechecker slowness test for array-of-ranges from slow to fast, yay
* Apply Doug's patch to loosen test to just check for error
The defaults we were generating for Collection and
BidirectionalCollection didn't make any sense, because if you could do
that strideable arithmetic then you essentially had random access.
Instead we constrain the defaults to apply to RandomAccessCollection
where the Indices are a CountableRange.
