Micro-Optimization
The final swap when picking the median is a micro-optimization that moves the pivot into the partition where it would eventually be placed, bypassing a needless comparison with itself.
Given the layout before the swap,
[ left . . . . . pivot . . . . . right ]
these facts,
left < pivot
pivot < right
pivot = pivot
and this partitioning logic:
for every element
if (element < pivot)
move element to left half
else
move element to right half
we can make some minor optimizations by skipping the comparison for left
, right
, and pivot
since we know into which partition they should land. The first two are already in their correct partitions, so we start by shifting in the looping terminals one slot. By performing a swap to place pivot
into the second-to-last slot, we can skip comparing it as well. Here it must be placed at the far right end of the partition, next to right
.
swap(arr, middle, right - 1);
which leaves this new layout:
[ left . . . . . . . . . . pivot right ]
^ partition these ^
If the partition comparison used <=
instead of <
, you'd swap the pivot into the second slot instead.
swap(arr, middle, left + 1);
[ left pivot . . . . . . . . . . right ]
^ partition these ^