There are two variations of insertion sort. You are comapring to the swapless insertion sort, the other poster is comparing to the swap basses insertion sort. This is the swap based insertion sort with a small variation.

As discussed, unlike insertion sort it begins by finding the max element and places it first.

Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".

> Following that it follows normal insertion sort pattern with one change. Insertion sort normally sorts the new element "downward". This sort sorts the new element "upward" from the smallest item. It still uses the same inline temporary slot that insertion sort uses, it's just more notable now because it's inserting the new item "bottom-up".

Well, the reason that's more notable is that doing it upward requires you to use swaps instead of an assignment chain. Going downward, you can remember the value you're going to insert all the way down the chain. Going upward, you're always placing the value you remember and then remembering a new value, which is much worse.

> If it was restricted to bubbling the maximum or minimum to the end of the list, the full sort would use one bubble, it would complete in linear time, and the list wouldn't be sorted afterwards.

Yes, one bubble op is linear time. A bubble sort is a sequence of bubble ops on the unsorted portion of the list (which shrinks by one for each bubble op).

Meanwhile an insertion sort is a sequence of insertion ops into the sorted portion of a list. So I agree with your analysis, except that the featured sort is a pessimized insertion sort, not a pessimized bubble sort.

> No, a bubble op bubbles one element into the correct position in a sorted list.

Again, that's an insertion op, not a bubble op. I suppose an insertion op can be thought of as equivalent to a bubble op on an element prepended to a sorted list, but it doesn't make sense to call it a bubble op in the context of bubble sort, since bubble sort doesn't do that.

> For our purposes, there is no difference, because we're bubbling into a perfectly sorted list, so once our initial element stops moving, nothing else can move.

I think this is where you're going wrong. In a bubble sort, a bubble op is never run on a sorted list + 1 element. Instead, it's run only on the unsorted portion of the list.