DSData Structures & Algorithms · Lesson 8 of 9

Sorting: How & When

Sorting is the most-studied problem in computer science, and the ideas inside the classic algorithms — divide and conquer, trading memory for speed — show up everywhere. You'll almost always call your language's built-in sort, but knowing what's under it makes you 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.

Python

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

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

Python

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]

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, cache-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.

Python

# 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]
◆ Note
That's the core toolkit: Big-O to measure, arrays and hash maps for storage, stacks and queues for order, recursion for self-similar problems, trees and graphs for connected data, sorting to impose order. From here, practice beats theory — pick easy problems on any practice site, and reach for the structure whose trade-offs fit. You now know them all.