Bubble, selection and insertion sort

Bubble sort swaps adjacent inversions and moves a large value to the end; a no-swap exit makes sorted input linear. Selection sort repeatedly picks the remaining minimum and still performs quadratic comparisons on sorted input. Insertion sort places each item in a sorted prefix and benefits from few inversions.

Stability preserves the original relative order of equal-key records. Insertion stays stable when shifting only strictly greater keys. Standard selection sort's distant swaps are unstable. In-place usually concerns auxiliary storage; count recursive stacks separately.

Insertion sort is useful for small runs in hybrid algorithms, but quadratic cost is unsuitable for huge inputs. Comparator consistency, NaN behaviour and locale ordering must be specified independently of the algorithm.

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        x, j = a[i], i-1
        while j >= 0 and a[j] > x:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = x
    return a
assert insertion_sort([4,2,3]) == [2,3,4]