Simple sorting

Sorting comes up everywhere, and it's the classic place to compare algorithms. Three simple ones are easy to do by hand.

Bubble sort walks through the list comparing neighbours and swapping any pair that's the wrong way round. After one pass the biggest value has bubbled to the end. Repeat until a pass makes no swaps.

Selection sort finds the smallest value and swaps it into first place, then the smallest of the rest into second place, and so on.

Insertion sort works like sorting a hand of cards: take each item in turn and slide it left into its place among the ones already sorted.

def insertion_sort(xs):
    xs = xs[:]
    for i in range(1, len(xs)):
        item = xs[i]
        j = i - 1
        while j >= 0 and xs[j] > item:
            xs[j + 1] = xs[j]
            j -= 1
        xs[j + 1] = item
    return xs

print(insertion_sort([5, 2, 4, 1, 3]))

All three are O(n²) in the worst case: for each item, they may look at all the others. That's fine for twenty items and hopeless for a million. Insertion sort has one strength: on a list that's already nearly sorted it does almost no work, close to O(n).