Auto merge of #29675 - bluss:merge-sort-fastpath, r=huonw

sort: Fast path for already sorted data

When merging two sorted blocks `left` and `right` if the last element in
`left` is <= the first in `right`, the blocks are already in sorted order.

Add this as an additional fast path by simply copying the whole left
block into the output and advancing the left pointer. The right block is
then treated the same way by the already present logic in the merge
loop.

Can reduce runtime of .sort() to less than 50% of the previous, if the data
was already perfectly sorted. Sorted data with a few swaps are also
sorted quicker than before. The overhead of one comparison per merge
seems to be negligible.

0 files changed, 0 insertions, 0 deletions