Re:Bubble Sort: An Archaeological Algorithmic Analysis
by nwallin on Wednesday February 06, 2019 @03:41PM
(#19099666)
> I think that variant is only faster than bubble sort because it stops iterating once the newly inserted item has reached its final resting place,
It's actually faster because of a subtler reason: branch prediction.
In insertion sort, the x[j-1] > x[j] comparison is almost always true. Insertion sort performs that comparison O(n^2) times, and it is false only n-1 times. So the branch predictor quickly identifies that it should just assume the comparison is true.
It's actually faster because of a subtler reason: branch prediction.
In insertion sort, the x[j-1] > x[j] comparison is almost always true. Insertion sort performs that comparison O(n^2) times, and it is false only n-1 times. So the branch predictor quickly identifies that it should just assume the comparison is true.