> 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 actual

> 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.