Your step 3 is an insertion op, not a bubble op.
An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element to the end of an unsorted list.
An insertion op inserts one element into a sorted list. A bubble op bubbles the maximum (or minimum) element to the end of an unsorted list.
You're correct that this is also a good match to insertion sort, but only conceptually.
(Note that one classic bubblesort pass moves several elements when the data is unsorted - when an element has bubbled as far as it can go, the bubblesort pass picks up the element that blocked it and carries that one further, and this process repeats until the end of the data is reached. 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.)
The bigger difference between an insertion op and a bubble op is in the number of assignments.
This is the chain of operations you get while bubbling:
swap(a5, a6)
swap(a4, a5)
swap(a3, a4)
temp = a6
a6 = a5
a5 = a4
a4 = a3
a3 = temp
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".
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 overwriting a value that you must immediately remember, which is worse.
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.