Insertion sort

Insertion sort works like when you arrange playing cards in your hand: you pick up the cards one by one and insert each into its right place among those already sorted. Unlike selection sort, here we build a sorted part by inserting elements one by one, not by searching for a global minimum.

The principle: for each element at position i (starting from i=1), you hold on to it (the « key »), then you shift to the right all the already-sorted elements that are greater than the key, and you finally place the key into the gap left free.

Diagram on [5, 2, 4, 1, 3]:

start   : [5, 2, 4, 1, 3]
step 1  : [2, 5, 4, 1, 3]   (insert 2 before 5)
step 2  : [2, 4, 5, 1, 3]   (insert 4 between 2 and 5)
step 3  : [1, 2, 4, 5, 3]   (insert 1 at the very beginning)
step 4  : [1, 2, 3, 4, 5]   (insert 3 between 2 and 4)

[ ...sorted... | key to insert | ...not yet seen... ]

In the worst case (array sorted in reverse), each insertion shifts almost all the elements already processed: this is again O(n²). But in the best case (array already sorted), each element is compared only once with its immediate neighbor: this is O(n), much faster. That is why insertion sort is often used for small arrays or nearly-sorted arrays.

def tri_insertion(a):
    a = a[:]
    for i in range(1, len(a)):
        cle = a[i]
        j = i - 1
        while j >= 0 and a[j] > cle:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cle
    return a

Classic pitfall: the condition j >= 0 must be checked BEFORE a[j] > cle in the while (otherwise Python tests a[-1] through the wrong ordering, or worse, in another language it runs past the end of the array).