fzort: I think you mean Binary Insertion Sort and not Bubble Sort. The idea would be to use another in-place sorting algorithm that doesn't get hit hard when attempting to sort a segment that may already be pre-sorted. No reason to use anything slower than you have to, and so Binary Insertion Sort fits nicely.

For historical reasons, a Binary Insertion Sort was probably also used to eliminate recursive function call overhead as well as stack overflows.

Note that while the binary search portion of the Binary Insertion Sort algorithm is recursive, since it is tail recursive, it can be implemented in such a way as to even avoid having to use an internal stack.

See the last implementation discussed here for an example on how to do that.

Thanks for the link too, btw, I will be sure to check that out later when I get home from work!