search

rust-lang / rust

Empowering everyone to build reliable and efficient software.
https://www.rust-lang.org
Other
97.99k stars 12.68k forks source link

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

Open hvenev-insait opened 5 months ago

hvenev-insait commented 5 months ago

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 a3065a1a34fe1c0b85bdf3ff1f3d0bd470235e6b, the shift was happening on v[i..] (instead of v[..i]), attempting to shift v[i] to the right, which makes more sense.

workingjubilee commented 5 months ago

have you considered opening a PR?

hvenev-insait commented 5 months ago

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 a3065a1a34fe1c0b85bdf3ff1f3d0bd470235e6b (probably call insertion_sort_shift_right on v[i..] instead of v[..i])?

Also, do we have any benchmarks for that code?