core::slice::sort::partial_insertion_sort: Redundant call to insertion_sort_shift_right

[hvenev-insait]

In partial_insertion_sort, an invariant is maintained that v[..i] is sorted. When a non-sorted pair v[i-1] > v[i] is encountered, they are swapped and the last element of v[..i] is shifted to the left into its correct spot. Then for some reason insertion_sort_shift_right is called on v[..i], attempting to shift v[0] to the right, which never does anything.

Before commit a3065a1, the shift was happening on v[i..] (instead of v[..i]), attempting to shift v[i] to the right, which makes more sense.

[workingjubilee]

have you considered opening a PR?

[hvenev-insait]

Not yet. I am not sure what the best way to fix this is. Do we want to maintain the current behavior (in which case all we need to do is delete insertion_sort_shift_right), or do we want to go back to the behavior before a3065a1 (probably call insertion_sort_shift_right on v[i..] instead of v[..i])?

Also, do we have any benchmarks for that code?