10. Sorting & Searching

Why Sort at All?

Sorting transforms a random collection into an ordered one, enabling:

• Binary search — $O(\log n)$ instead of $O(n)$
• Two-pointer techniques
• Duplicate detection
• Ranking and leaderboards

---

10.1 Python's Built-in Sort (Use This in Production)

Python uses Timsort — $O(n \log n)$ worst case, $O(n)$ for nearly-sorted data. It's stable (equal elements keep their original order) and highly optimised.

# Basic sort
nums = [5, 2, 8, 1, 9, 3]
nums.sort()              # in-place, returns None
sorted_copy = sorted(nums)  # returns new list, original unchanged

# Reverse
nums.sort(reverse=True)

# Sort by a key
words = ["banana", "fig", "apple", "kiwi"]
words.sort(key=len)              # sort by string length
words.sort(key=lambda w: w[-1]) # sort by last letter

# Sort objects by attribute
people = [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]
people.sort(key=lambda p: p["age"])   # youngest first

# Sort by multiple criteria (primary: age, tiebreak: name)
people.sort(key=lambda p: (p["age"], p["name"]))

# Custom dataclass
from dataclasses import dataclass, field

@dataclass(order=True)
class Task:
    priority: int     # sort by this first
    name: str = field(compare=False)

tasks = [Task(3, "low"), Task(1, "high"), Task(2, "medium")]
tasks.sort()   # Task(1,'high'), Task(2,'medium'), Task(3,'low')

---

10.2 How Sorting Algorithms Work

You don't need to implement these in production Python, but understanding them helps you reason about performance.

# --- Merge Sort — Divide & Conquer --- O(n log n)
# Split in half → sort each half → merge sorted halves
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid   = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    # Merge two sorted lists
    result = []
    i = j  = 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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# --- Quick Sort — O(n log n) average --- elegant but O(n²) worst case
import random

def quick_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    lesser  = [x for x in arr if x < pivot]
    equal   = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(lesser) + equal + quick_sort(greater)

---

10.3 Binary Search

Requirement: Array must be sorted.
Idea: Compare the middle element to the target. Eliminate half the search space each step → $O(\log n)$.

# --- Manual binary search ---
def binary_search(arr: list[int], target: int) -> int:
    """Returns index of target, or -1 if not found."""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1    # target is in the right half
        else:
            right = mid - 1   # target is in the left half
    return -1

# --- Python's bisect module (preferred) ---
import bisect

arr = [1, 3, 5, 7, 9, 11]
bisect.bisect_left(arr, 7)    # 3 — index of 7 (or where 7 would go)
bisect.bisect_right(arr, 7)   # 4 — index AFTER 7
bisect.bisect_left(arr, 6)    # 3 — where 6 would be inserted to keep sorted

# Check if value exists in sorted list
def sorted_contains(arr: list[int], target: int) -> bool:
    i = bisect.bisect_left(arr, target)
    return i < len(arr) and arr[i] == target

# Find leftmost and rightmost occurrence
def search_range(arr: list[int], target: int) -> list[int]:
    left  = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target) - 1
    if left <= right and arr[left] == target:
        return [left, right]
    return [-1, -1]

print(search_range([5,7,7,8,8,10], 8))  # [3, 4]

---