Sorting and Searching

• Drop constants and lower terms: 3n² + 5n + 2 is O(n²)
• An upper bound on growth as n grows
• State which case it bounds: best, average or worst

• Space complexity = extra memory beyond the input
• In-place sorts use O(1) or O(log n) stack

• Stable: equal keys keep their original order
• In-place: no big auxiliary array
• Comparison sorts cannot beat Ω(n log n)

• Swap adjacent out-of-order pairs
• After pass k, the k largest are fixed at the end
• No swap in a full pass → stop: O(n) on sorted input

• A sorted prefix grows by one each step
• Larger elements shift right; no swaps

• Insertion wins on small or nearly sorted arrays
• Timsort and introsort use it for tiny partitions

• Split in half, sort each, merge two sorted halves with two pointers
• Always O(n log n), extra space O(n), stable
• Ties: take from the left half first (<=)
• < on ties breaks stability

if left[i] <= right[j]:
    out.append(left[i]); i += 1
else:
    out.append(right[j]); j += 1

<= keeps equal keys in order

• Pick a pivot, partition into smaller and larger, recurse
• Average O(n log n), worst O(n²)
• In place, O(log n) stack, not stable
• Worst case: sorted input with first/last pivot
• Fix: random or median-of-three pivot

• Build max-heap in O(n), then swap root with last and sift down
• O(n log n) always, O(1) space, not stable
• 0-based: children of i are 2i+1, 2i+2; parent is (i-1)/2
• Heapify from last non-leaf n/2-1 down to 0

• O(n + k) time and space
• Right-to-left placement makes it stable
• Only for integer keys in a small range k
• Base of radix sort

• Interview: why does heapify start at n/2-1? Later nodes are leaves.
• Interview: why is counting sort stable? Right-to-left keeps equal keys in order.

• Needs a sorted array; each step halves the range
• Time O(log n), space O(1) when iterative
• Mid is lo+(hi-lo)/2, not (lo+hi)/2: the sum overflows fixed-width ints

def binary_search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == t: return mid
        if a[mid] < t: lo = mid + 1
        else: hi = mid - 1
    return -1

returns -1 if not found

• Search on answer: binary search any monotonic predicate (min capacity, square root)
• Rotated array: one half is always sorted; check if the target lies in it, else go to the other half

• lo<=hi with hi=mid: infinite loop
• lo<hi with hi=mid-1: skips the answer

• Best case O(n): bubble (with early exit) and insertion on sorted input
• Merge and heap stay O(n log n) whatever the input

• O(log n), sorted input, loop while lo <= hi
• mid = lo + (hi - lo) / 2, never (lo + hi) / 2
• Lower bound = first index >= target (first occurrence)
• Upper bound = first index > target