Sorting

In most interviews you call Python's built-in sort and move on. You still need two things: fluency with key= and stability for multi-criteria sorts, and enough understanding of the classic algorithms to answer "implement merge sort", "why is quicksort $O(n^2)$ in the worst case?" or "which sort is stable?". This note covers both.

Python's built-in sort#

Python gives you two ways to sort:

Both use Timsort, a hybrid of merge sort and insertion sort that finds already-sorted runs in the data and merges them.

key=, reverse= and multi-key sorts#

words = ["banana", "Apple", "cherry", "date"]
print(sorted(words, key=str.lower))          # case-insensitive
print(sorted(words, key=len, reverse=True))  # longest first

people = [("Alice", 25), ("Bob", 20), ("Charlie", 25)]
# Age descending, then name ascending.
# Tuples compare element by element.
people.sort(key=lambda p: (-p[1], p[0]))
print(people)   # [('Alice', 25), ('Charlie', 25), ('Bob', 20)]

counts = {"a": 3, "b": 1, "c": 2}
# sort a dict by value
print(sorted(counts.items(), key=lambda kv: kv[1]))

Negating only works for numbers. To sort strings descending inside a multi-key sort, use stability: sort by the secondary key first, then by the primary key.

people = [("Bob", 25), ("Alice", 25), ("Cara", 20)]
# secondary key first: name descending
people.sort(key=lambda p: p[0], reverse=True)
# then the primary key: age ascending (stable keeps the name order)
people.sort(key=lambda p: p[1])
print(people)   # [('Cara', 20), ('Bob', 25), ('Alice', 25)]

When the order depends on comparing two items directly (e.g. Largest Number), write a comparator and wrap it:

from functools import cmp_to_key

nums = ["3", "30", "34", "5", "9"]
nums.sort(key=cmp_to_key(lambda a, b: -1 if a + b > b + a else 1))
print("".join(nums))   # 9534330

The classic algorithms at a glance#

Here is how the four classic sorts compare before you look at each one.

Quick sort's space is its recursion stack, $O(\log n)$ on average.

Bubble sort#

Walk the array comparing neighbours and swap any pair that's out of order. Each pass carries the largest unsorted element to the end, so the unsorted range shrinks by one per pass.

Tracing [5, 3, 8, 1, 2]:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # the last i items are already in place
        for j in range(n - i - 1):
            # strict > keeps equal items in order (stable)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # a pass with no swaps means sorted: O(n) best case
        if not swapped:
            break
    return arr

When to use: practically never. It's the baseline other sorts are compared against.

Insertion sort#

Like sorting cards in your hand: take the next element, slide every bigger element in the sorted prefix one step right, and drop the element into the gap.

Tracing [5, 3, 8, 1, 2] (the bar | separates the sorted prefix from the rest):

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:   # shift bigger items right
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key                 # drop key into the gap
    return arr

• Best case $O(n)$: on sorted input each element is compared once and never moves.
• Worst case $O(n^2)$: on reverse-sorted input every element slides to the front, $1 + 2 + \dots + (n-1)$ moves.
• Why it beats bubble sort: it stops as soon as the element is in place, so nearly-sorted data costs close to $O(n)$.

When to use: small arrays, nearly-sorted data, or data that arrives one item at a time. Timsort uses it for short runs.

Merge sort#

Split the array in half until pieces have one element (already sorted), then merge sorted halves back together.

Merging two sorted lists uses two pointers: compare the front items, take the smaller, advance that pointer. When one side runs out, append the rest of the other.

Merging left = [3, 5] with right = [1, 2, 8]:

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

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= takes from the left on ties: stable
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # at most one of these is non-empty
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Why $O(n \log n)$: each level of splitting merges all $n$ elements once, and halving gives $\log_2 n$ levels (about 20 for a million items). For a million elements that's around $2 \times 10^7$ steps versus $10^{12}$ for an $O(n^2)$ sort.

Trade-off: the merge needs a new array, so extra space is $O(n)$.

When to use:

• You need a guaranteed $O(n \log n)$ or a stable sort.
• Sorting a linked list: merging just relinks nodes, so no extra array is needed (Sort List).
• External sorting: data larger than memory. Sort chunks that fit, then merge them from disk.
• The merge step itself is a pattern: Merge Two Sorted Lists, Merge k Sorted Lists, counting inversions.

Quick sort#

Pick a pivot, partition so smaller items go left and larger go right, and the pivot lands in its final position. Recurse on both sides.

Partition (Lomuto scheme)#

i marks the end of the "≤ pivot" zone. j scans; whenever arr[j] <= pivot, grow the zone and swap arr[j] into it. Finally, swap the pivot just after the zone.

Tracing [5, 3, 8, 1, 2] with pivot = 2 (the last item) and i = -1:

Pivot 2 is now in its final position. Recurse on [1] and [8, 5, 3].

import random

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        p = partition(arr, low, high)
        quick_sort(arr, low, p - 1)
        quick_sort(arr, p + 1, high)
    return arr

def partition(arr, low, high):
    # a random pivot avoids the sorted-input worst case
    r = random.randint(low, high)
    arr[r], arr[high] = arr[high], arr[r]
    pivot = arr[high]
    i = low - 1        # end of the "<= pivot" zone
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

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

Average $O(n \log n)$: a reasonable pivot splits the range roughly in half, giving about $\log n$ levels of $O(n)$ partitioning.

Worst $O(n^2)$: if the pivot is always the smallest or largest item (for example, "last element" pivot on already-sorted input), each level only removes one element, giving $n$ levels. A random pivot makes this extremely unlikely.

Why it's often faster than merge sort in practice: it partitions in place (no new arrays per level) and scans memory sequentially, which suits CPU caches.

The pattern beyond sorting: partitioning alone gives quickselect, which finds the k-th smallest element in $O(n)$ average time (Kth Largest Element in an Array, K Closest Points). Recurse only into the side that contains index k.

Quick sort vs merge sort#

Both are $O(n \log n)$ on average, but they make different trade-offs.

What real libraries use:

• Python list.sort: Timsort (merge + insertion, stable).
• Other runtimes often use dual-pivot quicksort for arrays of primitives and Timsort for objects, which need stability.
• C++ std::sort: introsort (quicksort that falls back to heapsort when recursion gets too deep).

Key takeaways#

• Use sorted()/.sort() with key=; tuple keys and stability handle multi-criteria ordering.
• Python's sort is stable, $O(n \log n)$ worst case and $O(n)$ on sorted input.
• Insertion sort shines on small or nearly-sorted data; bubble sort is only a baseline.
• Merge sort: guaranteed $O(n \log n)$, stable, $O(n)$ space, ideal for linked lists.
• Quick sort: in place and fast on average, $O(n^2)$ worst case; randomise the pivot. Its partition step powers quickselect.