7. Sorting

Key Insight

Python's sorted() / .sort() (Timsort) is your default. Only implement custom sorts when you need $O(n)$ linear sorts (counting/radix) or when the problem tests sort mechanics (merge sort for inversion count).

Complexity Reference

Algorithm	Best	Average	Worst	Space	Stable
Timsort (Python)	$O(n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes
Merge sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Yes
Quick sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	No
Counting sort	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	Yes
Radix sort	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+k)$	Yes

---

7.1 Python Sort Idioms

# Sort by multiple keys — tuples are compared lexicographically
intervals = [[2,6],[1,3],[8,10],[15,18]]
intervals.sort(key=lambda x: (x[0], x[1]))

# Sort descending
arr.sort(reverse=True)
sorted_arr = sorted(arr, reverse=True)

# Sort by absolute value
arr.sort(key=abs)

# Sort strings by length then alphabetically
words.sort(key=lambda w: (len(w), w))

# Custom comparison (use functools.cmp_to_key)
from functools import cmp_to_key
def cmp(a, b):          # return negative if a < b, 0 if equal, positive if a > b
    return (a+b > b+a) - (a+b < b+a)   # largest number from array
nums.sort(key=cmp_to_key(cmp))

---

7.2 Merge Sort (+ Inversion Count)

def merge_sort(arr: list[int]) -> tuple[list[int], int]:
    """Returns sorted array and number of inversions."""
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, l_inv = merge_sort(arr[:mid])
    right, r_inv = merge_sort(arr[mid:])
    merged = []
    inversions = l_inv + r_inv
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i   # all remaining left elements > right[j]
    merged.extend(left[i:]); merged.extend(right[j:])
    return merged, inversions

---

7.3 Quick Sort (Lomuto partition)

import random

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

def partition(arr: list[int], lo: int, hi: int) -> int:
    # Randomise to avoid O(n²) on sorted input
    pivot_pos = random.randint(lo, hi)
    arr[pivot_pos], arr[hi] = arr[hi], arr[pivot_pos]
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[hi] = arr[hi], arr[i+1]
    return i + 1

# Quickselect — O(n) average kth smallest
def kth_smallest(arr: list[int], k: int) -> int:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        p = partition(arr, lo, hi)
        if p == k - 1:
            return arr[p]
        elif p < k - 1:
            lo = p + 1
        else:
            hi = p - 1
    return -1

---

7.4 Counting Sort & Bucket Sort

# --- Counting sort (integers in range [0, k]) ---
def counting_sort(arr: list[int], k: int) -> list[int]:
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1
    result = []
    for val, cnt in enumerate(count):
        result.extend([val] * cnt)
    return result

# --- Bucket sort (floats in [0, 1)) ---
def bucket_sort(arr: list[float]) -> list[float]:
    n = len(arr)
    buckets: list[list] = [[] for _ in range(n)]
    for x in arr:
        buckets[int(x * n)].append(x)
    result = []
    for b in buckets:
        result.extend(sorted(b))
    return result

---