Nate Cook e5c1567957 [stdlib] Switch to a stable sort algorithm (#19717) ...

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.

2018-11-07 00:05:04 -06:00

5.4 KiB

Raw Permalink Blame History

View Raw