Appropriate insertion sorting algorithm
Bubble or Insert?

#1 and #2 are both implementations of insertion sort (*).  The way you insert the element is not so important: whether you copy one by one, use arraycopy, or bubble it down is up to implementation.  I'd imagine arraycopy to be the best for larger inputs.

#3 would be closer to selection sort, a relative of insertion sort, though there's no advantage in allocating a new array. (Or maybe I misunderstand.)

Both build a sorted part in the array, guaranteeing that at step i, array[0..i] is sorted.  Both do their sorting in-line, not requiring extra array allocations.  And both select an element from the unsorted part and then insert it.  The difference between insertion and selection is in how they select the next element to be inserted.

Insertion sort doesn't care which element is next, so it selects whichever.

Selection sort specifically select the littlest element from the rest of the array.  This makes it more costly, but adds the additional guarantee that not only is array[0..i] in order, but it also contains the littlest elements of the entire array.

(*) Though #1 is related to bubble sort in a way his parents won't talk about.

Optimise?

A strong point of insertion sort is that it performs very well for input that is already (mostly) sorted.

#1 unconditionally runs in quadratic time: i:[0..len-2], j:[i+1..0], which is in the order of n² - n steps.

#2 is smarter about it, and doesn't run back comparing if it won't need to.  This means it has the potential to run in close to linear time.  Specifically, it will be in the order of n + d*n steps, with d being the number of elements out of order.

#1 can be 'fixed' with a simple addition:

for (...) { 
    for (...) {
        if (cond) {
            swap;
        } else {
            break; // &lt;-- 
        }
    }
}


... or, depending on your style preference:

for (...) { 
    for (... &amp;&amp; cond) { // &lt;-- as in #2
        if (cond) {
            swap;
        }
    }
}


... after which it's pretty much the same as #2.