Lesson 8 of 9

Sorting: How & When

You'll see how the classic sorting work and why the fast ones are O(n log n). In practice you'll call your language's built-in sort, and this lesson shows how to use it well.

The simple sorts are O(n²): bubble sort repeatedly swaps neighbors that are out of order; insertion sort takes each item and slides it back into place among the already-sorted prefix (how people sort cards — and genuinely good on small or nearly-sorted data). They're worth reading once to see why they're slow: both compare almost every pair.


def insertion_sort(items):            # O(n^2) worst, O(n) if nearly sorted
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]   # slide bigger items right
            j -= 1
        items[j + 1] = current
    return items
Python (loads on first run)Ctrl+Enter runs

The fast sorts hit O(n log n) with divide and conquer plus . Merge sort: split the in half, recursively sort each half, then merge two sorted halves in one linear pass. The log n comes from halving (like search), the n from merging each level. It's the cleanest recursive algorithm in this track.


def merge_sort(items):
    if len(items) <= 1:                    # base case
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])         # trust the recursion
    right = merge_sort(items[mid:])
    return merge(left, right)

def merge(a, b):                           # two sorted lists -> one
    result, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i]); i += 1
        else:
            result.append(b[j]); j += 1
    return result + a[i:] + b[j:]

merge_sort([38, 27, 43, 3, 9, 82, 10])
# [3, 9, 10, 27, 38, 43, 82]
Python (loads on first run)Ctrl+Enter runs

Quicksort is merge sort's rival: pick a pivot, partition items into smaller-than and bigger-than, recurse on each side. Faster in practice (in-place, -friendly) but O(n²) worst case on adversarial input. Real standard libraries use hybrids — Python's sorted() uses Timsort (merge sort + insertion sort, exploits already-sorted runs), and it's stable: equal items keep their original order, so you can sort by one key then another.


# In practice: use the built-in, master the key parameter.
people = [('ada', 36), ('linus', 55), ('grace', 85), ('ken', 55)]

sorted(people, key=lambda p: p[1])              # by age
sorted(people, key=lambda p: p[1], reverse=True)
sorted(people, key=lambda p: (p[1], p[0]))      # age, then name

# Sorting as a TOOL — many problems become easy after sorting:
# duplicates become adjacent, min/max hit the ends,
# and binary search (trees lesson) becomes available: O(log n) lookups.
nums = sorted([5, 3, 8, 3, 1])       # [1, 3, 3, 5, 8]
Python (loads on first run)Ctrl+Enter runs
Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.