When used as an algorithm (as opposed to a sorting network), insertion sort only inserts "as far as it needs to". In other words: it moves the new element to th

When used as an algorithm (as opposed to a sorting network), insertion sort only inserts "as far as it needs to". In other words: it moves the new element to the correct position, then stops going back through the array. This is the aspect of insertion sort that makes it very fast for "almost sorted" data: each element is only moved a few spots. However, this is a branch that is difficult to predict: this is the author's point. For very small amounts of data, branch misprediction for this branch dominates. This is not the case when insertion sort is expressed as a sorting network. Take a look at this image [1]: the final "insert" has comparators that go through the entire network. The "algorithm" version wouldn't do that: it would stop (using a branch) as soon as the entry hits the correct place. If you remove that branch (which, remember, is the thing that makes insertion sort faster in the general case), insertion and bubble sort are indeed very similar. The point here is that "sorting algorithms" and "sorting networks" are not the same thing: a sorting algorithm can branch, a sorting network cannot. The same principles of bubbling and insertion can apply to both, but that does not mean that an insight that applies to sorting networks necessarily applies to sorting algorithms. [1]: https://en.wikipedia.org/wiki/Sorting_network#/media/File:Recursive-insertion-sorting-network.svg https://en.wikipedia.org/wiki/Sorting_network#/media/File:Re... (PS: I actually wrote most of that wikipedia article years ago! I did the illustrations too! I basically just wrote down and made diagrams for whatever I could understand from The Art of Computer Programming vol 3. The insight about how bubble sort and insertion sort are essentially the same when expressed as sorting network is from Knuth, though I doubt it's original with him)