Recursion and Divide-and-Conquer Interview Patterns: Merge Sort, Quick Select, and Power (2025)

Recursion Fundamentals

Every recursive solution has: a base case (stops the recursion), a recursive case (reduces the problem), and a trust-and-use pattern (trust that the recursive call returns the correct answer for the subproblem, then use it). The call stack depth = recursion depth. For O(n) depth: risk of stack overflow on large inputs — consider iteration with an explicit stack. Tail recursion: the recursive call is the last operation — some compilers optimize this to iteration (Python does NOT). Master theorem for divide-and-conquer: T(n) = aT(n/b) + f(n). Common cases: T(n) = 2T(n/2) + O(n) → O(n log n) (merge sort). T(n) = T(n/2) + O(1) → O(log n) (binary search). T(n) = 2T(n/2) + O(1) → O(n) (tree traversal).

Merge Sort — O(n log n) Stable Sort

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums)  list[int]:
    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

# Count inversions using merge sort (number of pairs i nums[j])
def count_inversions(nums: list[int]) -> tuple[list[int], int]:
    if len(nums) <= 1:
        return nums, 0
    mid = len(nums) // 2
    left, left_inv = count_inversions(nums[:mid])
    right, right_inv = count_inversions(nums[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, left_inv + right_inv + split_inv

def merge_count(left, right):
    result, inv = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i]  right[j]
            j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result, inv

Quick Select — O(n) Average k-th Smallest

import random

def find_kth_smallest(nums: list[int], k: int) -> int:
    def partition(lo, hi) -> int:
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] <= pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        return store

    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        pivot = partition(lo, hi)
        if pivot == k - 1:
            return nums[pivot]
        elif pivot < k - 1:
            lo = pivot + 1
        else:
            hi = pivot - 1
    return -1

Fast Power (Exponentiation by Squaring)

def my_pow(x: float, n: int) -> float:
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n % 2 == 1:
            result *= x
        x *= x
        n //= 2
    return result
# O(log n): square x on each iteration, halve n

Subsets, Permutations, and Combinations

# Subsets (LC 78): generate all 2^n subsets
def subsets(nums: list[int]) -> list[list[int]]:
    result = [[]]
    for n in nums:
        result += [subset + [n] for subset in result]
    return result

# Permutations (LC 46)
def permutations(nums: list[int]) -> list[list[int]]:
    if not nums: return [[]]
    result = []
    for i, n in enumerate(nums):
        rest = nums[:i] + nums[i+1:]
        for perm in permutations(rest):
            result.append([n] + perm)
    return result

# Combinations (LC 77): choose k from n
def combine(n: int, k: int) -> list[list[int]]:
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            # Pruning: not enough elements remaining
            if n - i + 1 < k - len(current):
                break
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Coinbase Interview Prep