> 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

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