Sorting algorithms

Why it matters

Sorted data makes many problems easy: binary search, finding duplicates, merging records, ranking. In real code you will almost always call sorted() or .sort(), which are fast and well tested. Writing two sorts yourself is still worth it: it is the clearest way to see the difference between O(n^2) and O(n log n), and the ideas (insert into a sorted part, split and merge) come back in many other algorithms.

Insertion sort

Think of sorting a hand of playing cards. You keep the left part of your hand sorted and take one new card at a time, sliding it left until it sits in the right place.

def insertion_sort(items):
    result = list(items)              # copy so we do not change the input
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0 and result[j] > current:
            result[j + 1] = result[j]  # shift the bigger item right
            j -= 1
        result[j + 1] = current        # drop current into the gap
    return result

Trace [5, 2, 4, 1]:

Cost. In the worst case (reverse-sorted input) each new item shifts past every item before it: 1 + 2 + ... + (n-1), about n^2 / 2 steps, so O(n^2). On a list that is already sorted, the inner loop never runs and it is O(n). That makes insertion sort good for small or nearly-sorted lists; Python's built-in sort uses it on short runs.

Merge sort

Merge sort is divide and conquer:

1. If the list has 0 or 1 items, it is already sorted (the base case).
2. Split it into two halves.
3. Sort each half (by calling merge sort on it).
4. Merge the two sorted halves into one sorted list.

The key piece is merge. Both inputs are sorted, so the smallest remaining item is always at the front of one of them.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])    # one side may have leftovers
    result.extend(right[j:])
    return result


def merge_sort(items):
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))

Trace merge([2, 5, 9], [1, 6]): compare 2 and 1, take 1; compare 2 and 6, take 2; 5 and 6, take 5; 9 and 6, take 6; right is empty, so add the leftover 9. Result [1, 2, 5, 6, 9].

Cost. Each level of splitting does O(n) work in total to merge, and halving gives about log n levels. So merge sort is O(n log n) in every case, best and worst. For 100,000 items that is about 1.7 million steps versus about 5 billion for insertion sort's worst case. The cost is O(n) extra memory for the merged lists.

Using <= (not <) in merge keeps equal items in their original order. That property is called stability, and it matters when you sort records by one field after another.

What Python does

sorted() uses Timsort, a hybrid of merge sort and insertion sort. It is O(n log n), stable and very fast on real data, which often has sorted runs. Use it in production code. You can sort by a key:

people = [("Ada", 36), ("Linus", 21), ("Grace", 45)]
by_age = sorted(people, key=lambda p: p[1])

Common mistakes

• Forgetting leftovers in merge. When one side runs out, the rest of the other side must be added.
• No base case. merge_sort on a one-item list must return immediately or it recurses forever.
• Changing the input by accident. If the caller did not ask for an in-place sort, work on a copy.
• Assuming O(n^2) is always bad. For 10 items, insertion sort is fine and simple.

Quick recap

• Insertion sort: grow a sorted prefix one item at a time. O(n^2) worst, O(n) on sorted input.
• Merge sort: split, sort halves, merge. O(n log n) always, O(n) extra memory, stable with <=.
• In real code, call sorted().

Try it

In the Do tab, merge_sort is written for you. Write merge and insertion_sort; the checks compare your results with sorted() on random lists, duplicates, negatives and edge cases.