Sorting Algorithms

How sorting works under the hood, and when to write your own vs use built-ins

Knowledge Debt detected

You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.

Big-O Notation0%

Explanation

Understanding sorting means understanding the tradeoffs behind the algorithms you use every day.

Python's built-in sort — use it:

```python nums = [3, 1, 4, 1, 5, 9, 2, 6] nums.sort() # in-place, O(n log n) sorted_copy = sorted(nums) # returns new list

# Custom key — sort by anything people = [("Alice", 30), ("Bob", 25), ("Carol", 35)] people.sort(key=lambda p: p[1]) # by age: [("Bob",25), ("Alice",30), ("Carol",35)]

from operator import itemgetter, attrgetter people.sort(key=itemgetter(1)) # same, more efficient ```

Why Python's sort is O(n log n) — Timsort:

Timsort is a hybrid of merge sort and insertion sort. It exploits existing sorted runs in real data — often faster than O(n log n) in practice.

The algorithms you should understand conceptually:

Bubble sort — O(n²):

python def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]

Merge sort — O(n log n), stable:

```python def merge_sort(arr): 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, right): result, i, j = [], 0, 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 return result + left[i:] + right[j:] ```

Quicksort — O(n log n) average, O(n²) worst:

Partitions around a pivot. In-place, cache-friendly — fast in practice despite worse worst-case.

When to know which:

Default: use Python's sorted() — Timsort beats hand-rolled implementations
Need to sort once, then binary search repeatedly: sort + bisect
Counting sort / radix: O(n) for integers in a known range

Examples

Multi-key sorting

Negative sign trick for descending sort without reversing

students = [
    {"name": "Alice", "grade": 90, "age": 20},
    {"name": "Bob",   "grade": 90, "age": 22},
    {"name": "Carol", "grade": 85, "age": 19},
]

# Sort by grade desc, then age asc
students.sort(key=lambda s: (-s["grade"], s["age"]))
# [{"Alice",90,20}, {"Bob",90,22}, {"Carol",85,19}]

# Multiple keys with operator
from operator import itemgetter
students.sort(key=itemgetter("grade", "age"))

bisect for O(log n) insertion into sorted list

bisect implements binary search on sorted lists — O(log n) instead of O(n)

import bisect

scores = [10, 20, 30, 40, 50]

# Find insertion point (O(log n))
pos = bisect.bisect_left(scores, 35)   # 3

# Insert maintaining sort (O(n) due to shift, but search is O(log n))
bisect.insort(scores, 35)
print(scores)  # [10, 20, 30, 35, 40, 50]

# Fast "is x in sorted list?" via binary search
def binary_search(arr, target):
    idx = bisect.bisect_left(arr, target)
    return idx < len(arr) and arr[idx] == target

Next in Algorithms & Data Structures

Recursion Patterns

Continue

Unlocks

Binary Search