08. Sorting Algorithms

Sorting is the most studied problem in computer science. Not because sorting itself is hard — but because the techniques (divide-and-conquer, partitioning, merging) appear everywhere else. Understanding merge sort teaches you divide-and-conquer. Understanding quicksort teaches you partitioning. Understanding when O(n log n) is optimal teaches you lower bounds.

Why O(n log n)?

Any comparison-based sort must be Ω(n log n) in the worst case. There are n! possible orderings, and each comparison eliminates at most half. You need at least log₂(n!) ≈ n log n comparisons to distinguish all orderings.

This means: merge sort and quicksort (average) are optimal. You can't do better with comparisons alone.

Python's Built-in Sorting

Python's sorted() and list.sort() use Timsort — a hybrid of merge sort and insertion sort. It's O(n log n) worst case, stable, and highly optimized for real-world data (especially partially sorted data).

nums = [5, 2, 8, 1, 9]
sorted(nums)           # returns new list: [1, 2, 5, 8, 9]
nums.sort()            # sorts in-place, returns None

sorted() — returns a new list, works on any iterable. list.sort() — sorts in-place, only works on lists, slightly faster (no copy).

Sorting with key=

The key parameter transforms each element before comparison. The transformation is called once per element, not once per comparison — this is efficient.

# Sort strings by length
words = ["banana", "pie", "watermelon", "fig"]
sorted(words, key=len)  # ['pie', 'fig', 'banana', 'watermelon']

# Sort by absolute value
nums = [-5, 3, -2, 8, -1]
sorted(nums, key=abs)  # [-1, -2, 3, -5, 8]

# Sort tuples by second element
pairs = [(1, 'b'), (2, 'a'), (3, 'c')]
sorted(pairs, key=lambda x: x[1])  # [(2, 'a'), (1, 'b'), (3, 'c')]

Multiple criteria — return a tuple from the key function. Python compares tuples element by element:

# Sort by length first, then alphabetically
words = ["banana", "apple", "fig", "pea"]
sorted(words, key=lambda w: (len(w), w))
# ['fig', 'pea', 'apple', 'banana']

Reverse one criterion — negate numeric values, or use reverse=True for the whole sort:

# Descending sort (whole list)
nums = [3, 1, 4, 1, 5]
sorted(nums, reverse=True)  # [5, 4, 3, 1, 1]

# Sort by score descending, then name ascending (multi-criteria)
students = [("Alice", 90), ("Bob", 90), ("Charlie", 85)]
sorted(students, key=lambda s: (-s[1], s[0]))
# [('Alice', 90), ('Bob', 90), ('Charlie', 85)]
# Negate score for descending; string stays ascending naturally

Custom Comparators with functools.cmp_to_key

Sometimes you can't express the sort order with a key function — you need to compare two elements directly. Python 3 removed the cmp parameter, but functools.cmp_to_key bridges the gap.

A comparator returns:

• Negative if a should come before b
• Zero if equal
• Positive if a should come after b

LeetCode 179 - Largest Number

from functools import cmp_to_key

def largest_number(nums: list[int]) -> str:
    strs = [str(n) for n in nums]

    def compare(a: str, b: str) -> int:
        if a + b > b + a:
            return -1   # a should come first
        elif a + b < b + a:
            return 1    # b should come first
        return 0

    strs.sort(key=cmp_to_key(compare))
    result = "".join(strs)
    return "0" if result[0] == "0" else result

Use cmp_to_key when the relative order of two elements depends on comparing them together, not on an independent property of each element.

Implementing Sorts From Scratch

Python's built-in sorted() uses Timsort (O(n log n), stable) — you'll never beat it in practice. But interviewers ask you to implement sorting algorithms to test your understanding of divide-and-conquer, recursion, and partitioning. The two you need to know:

Merge Sort

Divide the array in half, sort each half recursively, merge the two sorted halves.

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(a: list[int], b: list[int]) -> list[int]:
    result = []
    i = j = 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
    result.extend(a[i:])
    result.extend(b[j:])
    return result

Time: O(n log n) always — guaranteed, no worst case. Space: O(n) — needs temporary lists for merging. Stable: Yes — equal elements keep their original order.

Merge sort is the go-to when you need guaranteed O(n log n) or stability. It's also the basis for external sorting (sorting data that doesn't fit in memory).

LeetCode 56 - Merge Intervals

Given a list of intervals [[start, end], ...], merge all overlapping intervals. Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]. Sort by start, then greedily extend or start a new interval.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Quicksort

Pick a pivot, partition the array so everything smaller is on the left and everything larger is on the right, then recurse on each side. lo and hi are the left/right boundaries of the subarray being sorted — initial call is quick_sort(nums, 0, len(nums) - 1).

def quick_sort(nums: list[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return
    pivot_idx = partition(nums, lo, hi)
    quick_sort(nums, lo, pivot_idx - 1)
    quick_sort(nums, pivot_idx + 1, hi)

def partition(nums: list[int], lo: int, hi: int) -> int:
    pivot = nums[hi]  # choose last element as pivot
    i = lo
    for j in range(lo, hi):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[hi] = nums[hi], nums[i]
    return i

Time: O(n log n) average, O(n²) worst case (already sorted + bad pivot). Space: O(log n) — recursion stack only, sorts in-place. Stable: No — partitioning can reorder equal elements.

Quicksort is faster in practice than merge sort (better cache behavior, no extra allocation) despite the worse worst case.

Partition: The Key Insight

The partition step places the pivot in its final sorted position in O(n). This enables:

• Quickselect — find the kth smallest element in O(n) average without fully sorting

LeetCode 215 - Kth Largest Element in an Array

import random

def find_kth_largest(nums: list[int], k: int) -> int:
    target = len(nums) - k  # kth largest = (n-k)th smallest

    def quickselect(lo: int, hi: int) -> int:
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]

        pivot = nums[hi]
        i = lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]

        if i == target:
            return nums[i]
        elif i < target:
            return quickselect(i + 1, hi)
        else:
            return quickselect(lo, i - 1)

    return quickselect(0, len(nums) - 1)

Random pivot avoids O(n²) worst case on sorted input.

Comparison

Simple Sorts (O(n²))

Insertion sort — build the sorted portion one element at a time. Fast on nearly-sorted data (O(n) best case). Used as the base case in Timsort.

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

Sorting as a Preprocessing Step

Many problems become easier after sorting:

• Two Sum (sorted) → two pointers, O(n)
• Merge intervals → sort by start, then linear scan
• Meeting rooms → sort by start/end time
• Kth largest → sort and index (or quickselect for O(n))
• Anagram grouping → sort each word as a key

# Group anagrams — sorting as a key function
from collections import defaultdict

def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Counting Sort — O(n + k)

Comparison-based sorts (merge sort, quicksort) can't beat O(n log n). But if values come from a small, known range, you can sort in O(n) by counting occurrences instead of comparing elements.

def counting_sort(nums: list[int], max_val: int) -> list[int]:
    counts = [0] * (max_val + 1)
    for n in nums:
        counts[n] += 1

    result = []
    for val in range(len(counts)):
        result.extend([val] * counts[val])
    return result

# Sort grades (0-100): O(n + 100) = O(n)
counting_sort([85, 90, 72, 85, 90, 60], 100)

Time: O(n + k) where k = range of values. Space: O(k) for the counts array.

When to use:

• Values are integers in a bounded range (ages, grades, RGB values, LeetCode 75 Sort Colors)
• k is small relative to n

When NOT to use:

• Arbitrary integers (k could be billions)
• Strings or objects (need comparison-based sort)

This is why Top-K with bucket sort is O(n) — frequency is bounded by n, so buckets act as a counting sort on frequencies.

Practice Problems

Key Takeaways

• Comparison-based sorting has a lower bound of O(n log n) — merge sort and quicksort are optimal
• Python's sorted() uses Timsort — O(n log n), stable, optimized for real data
• key= transforms each element once — use lambdas, len, tuples for multi-criteria sorts
• functools.cmp_to_key bridges custom comparators — use when order depends on comparing pairs
• Merge sort: guaranteed O(n log n), stable, but uses O(n) extra space
• Quicksort: O(n log n) average, in-place, but O(n²) worst case — randomize the pivot
• Partition places one element in its final position — enables quickselect for O(n) kth element
• In practice, use sorted(). In interviews, know how merge sort and quicksort work.
• Sorting is often a preprocessing step that enables simpler algorithms