Chapter 10: Sorting Algorithms (Part 2)

Vol 2: Algorithm Forest Adventure · Station 10

---

Metadata Card

Attribute	Value
Difficulty	(Core)
Prerequisites	Sorting Part 1 (Chapter 9), Recursion, Heaps
Keywords	Quicksort Lomuto Partition Hoare Partition Heapsort Counting Sort Radix Sort Sorting Stability Comparison Lower Bound

---

Breakthrough · Origins

Quicksort (Lomuto Partition)

def quicksort_lomuto(arr, low, high):
    if low < high:
        p = partition_lomuto(arr, low, high)
        quicksort_lomuto(arr, low, p - 1)
        quicksort_lomuto(arr, p + 1, high)

def partition_lomuto(arr, low, high):
    pivot = arr[high]
    i = low - 1
    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

Heapsort

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        _sift_down(arr, 0, i)
    return arr

def _sift_down(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

Counting Sort

def counting_sort(arr):
    if not arr:
        return []
    k = max(arr)
    counts = [0] * (k + 1)
    for num in arr:
        counts[num] += 1
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]
    output = [0] * len(arr)
    for num in reversed(arr):
        output[counts[num] - 1] = num
        counts[num] -= 1
    return output

Comparison Lower Bound

Any comparison-based sort requires at least Ω(n log n) comparisons in the worst case. Counting sort beats this by not using comparisons at all.

Stability Summary

Stable	Unstable
Bubble	Selection
Insertion	Shell
Merge	Quicksort
Counting	Heapsort
Radix

---

Verification Checklist

• [ ] Can hand-write quicksort (Lomuto partition)
• [ ] Can hand-write heapsort (build heap + extract)
• [ ] Can explain when to use counting sort
• [ ] Can determine if any sort is stable
• [ ] Can explain the comparison lower bound

---

Traveler's Notes

• Quicksort: fastest average, but input-sensitive with O(n²) worst
• Heapsort: guaranteed O(n log n), O(1) space, but slower in practice
• Linear sorts: not magic — they trade comparison for data feature exploitation
• Comparison lower bound: O(n log n) isn't a bug, it's a feature telling you when to change approach

---

→ Next Stop Preview

Chapter 11: Search and String Matching — "Binary search, KMP, Trie — finding needles in haystacks."