Prerequisite: Data Structures: Arrays to Queues

Sorting is one of the most studied problems in computer science - not because it is exotic, but because it shows up everywhere. Databases keep rows sorted for fast queries. Binary search only works on sorted input. Rendering engines sort objects by depth. Understanding sorting algorithms teaches you how to think about divide-and-conquer, stability, and the trade-offs between simplicity and speed.

Python’s Built-In Sort

Before building anything from scratch, know that Python ships with an excellent sort. Use it in production code.

numbers = [5, 2, 8, 1, 9, 3]

# In-place: modifies the list, returns None
numbers.sort()
print(numbers)   # [1, 2, 3, 5, 8, 9]

# Non-destructive: returns a new sorted list
original = [5, 2, 8, 1]
sorted_copy = sorted(original)
print(original)      # [5, 2, 8, 1] - unchanged
print(sorted_copy)   # [1, 2, 5, 8]

The key= parameter lets you sort by any attribute or transformation:

words = ["banana", "fig", "apple", "date"]
words.sort(key=len)             # sort by length
print(words)   # ['fig', 'date', 'apple', 'banana']

words.sort(key=str.lower)       # sort case-insensitively

Under the hood, Python uses Timsort - a hybrid of merge sort and insertion sort that achieves $O(n \log n)$ worst case and $O(n)$ on nearly-sorted data.

Bubble Sort

Bubble sort repeatedly swaps adjacent elements that are out of order. After each full pass, the largest unsorted element “bubbles” to its correct position.

def bubble_sort(arr: list[int]) -> list[int]:
    arr = arr[:]   # work on a copy
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 2, 8, 1]))   # [1, 2, 5, 8]

Time complexity: $O(n^2)$ in the worst and average case. It is easy to implement and understand, which makes it useful for teaching - but never use it on real data.

Insertion Sort

Insertion sort builds the sorted portion of the array one element at a time, inserting each new element into its correct position.

def insertion_sort(arr: list[int]) -> list[int]:
    arr = arr[:]
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 8, 1]))   # [1, 2, 5, 8]

Worst case is $O(n^2)$, but on nearly-sorted data it runs in $O(n)$ because very few shifts are needed. Timsort exploits this by using insertion sort on small subarrays. For fewer than ~10 elements, insertion sort often beats more complex algorithms due to lower overhead.

Merge Sort

Merge sort is the canonical divide-and-conquer sorting algorithm:

  1. Split the array in half.
  2. Recursively sort each half.
  3. Merge the two sorted halves into one sorted array.
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    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:])
    result.extend(right[j:])
    return result

print(merge_sort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

Merge sort guarantees $O(n \log n)$ in all cases (best, average, worst). It is also stable: equal elements preserve their original relative order. The cost is extra memory - the merge step allocates new arrays, so space complexity is $O(n)$.

Quicksort

Quicksort picks a pivot element, partitions the array so all smaller elements come before it and all larger elements come after, then recursively sorts each partition.

def quicksort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left  = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quicksort(left) + mid + quicksort(right)

print(quicksort([5, 2, 8, 1, 9, 3]))   # [1, 2, 3, 5, 8, 9]

Average case is $O(n \log n)$, but the worst case - a bad pivot choice on already-sorted data - is $O(n^2)$. In practice, with random or median-of-three pivot selection, quicksort is very fast and cache-friendly. Python’s sorted() uses Timsort rather than quicksort, but many other languages' standard libraries do use quicksort variants.

Stability

A sort is stable if equal elements maintain their original order. This matters when you sort by one key first, then by another:

students = [
    {"name": "alice", "grade": "B"},
    {"name": "bob",   "grade": "A"},
    {"name": "carol", "grade": "B"},
]

# Sort by grade first (Python's sort is stable)
students.sort(key=lambda s: s["grade"])
# Within same grade, original order is preserved:
# bob (A), alice (B), carol (B)
print([s["name"] for s in students])   # ['bob', 'alice', 'carol']

Merge sort is stable. Quicksort (as typically implemented) is not. Python’s sort is stable.

Examples

Sort a List of Dicts by Multiple Fields

import functools

records = [
    {"name": "alice", "score": 90, "age": 25},
    {"name": "bob",   "score": 85, "age": 30},
    {"name": "carol", "score": 90, "age": 22},
    {"name": "diana", "score": 85, "age": 28},
]

# Sort by score descending, then by age ascending
records.sort(key=lambda r: (-r["score"], r["age"]))

for r in records:
    print(r["name"], r["score"], r["age"])
# carol 90 22
# alice 90 25
# diana 85 28
# bob   85 30

Custom Sort Order

Use functools.cmp_to_key when you have a comparison function returning -1, 0, or 1:

import functools

def compare_by_last_name(a: str, b: str) -> int:
    last_a = a.split()[-1]
    last_b = b.split()[-1]
    if last_a < last_b:
        return -1
    elif last_a > last_b:
        return 1
    return 0

names = ["Alice Zhao", "Bob Adams", "Carol Liu", "David Brown"]
names.sort(key=functools.cmp_to_key(compare_by_last_name))
print(names)   # ['Bob Adams', 'David Brown', 'Carol Liu', 'Alice Zhao']

Algorithm Comparison

Algorithm Best Average Worst Stable Notes
Bubble sort $O(n)$ $O(n^2)$ $O(n^2)$ Yes Teaching only
Insertion sort $O(n)$ $O(n^2)$ $O(n^2)$ Yes Good for small or nearly-sorted
Merge sort $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ Yes Uses $O(n)$ extra space
Quicksort $O(n \log n)$ $O(n \log n)$ $O(n^2)$ No Fast in practice
Timsort (Python) $O(n)$ $O(n \log n)$ $O(n \log n)$ Yes Best of merge + insertion

In practice: use sorted() or .sort(). Study the rest to understand algorithmic thinking - the divide-and-conquer pattern in merge sort reappears in binary search, fast Fourier transforms, and many other places.

Read Next: Divide and Conquer