It is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.

That's not part of the definition of bubble sort.

It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.)

The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.

It is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.

not clrs

In any case, you should retract you claim that Bubble Sort is slower on already sorted case. It is CS101, that bubble sort is one of the fastest in this case.

oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list

it should say

    if (tmp >= a[j-1]) break;

however, this doesn't make it fail to terminate, which is a possible reading of your bug report