Divide and Conquer Interview Patterns: Merge Sort, Quick Select, Master Theorem

By /

The Divide and Conquer Paradigm

Divide and conquer solves problems by: (1) Divide — split the problem into smaller subproblems of the same type. (2) Conquer — solve each subproblem recursively (base case: problem is small enough to solve directly). (3) Combine — merge the subproblem solutions into the overall solution. The approach yields O(n log n) algorithms for problems where naive approaches are O(n²) — sorting, closest pair of points, fast exponentiation, and matrix multiplication.

Merge Sort

Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves. The merge step is O(n) — two pointers scan both sorted halves and place elements in order. Total time: T(n) = 2T(n/2) + O(n) = O(n log n) by the Master Theorem. Space: O(n) for the merge buffer (unlike quicksort, which is O(log n) space for the call stack).

Key applications: (1) Count inversions (LC 315, 493): an inversion is a pair (i,j) where i<j but nums[i]>nums[j]. During merge, when elements from the right half are placed before elements from the left half, each such placement contributes (left half remaining) inversions. Modify merge to count during the merge step. (2) Sort linked list in O(n log n) — merge sort is preferred over quicksort for linked lists since random access is O(n) but merge is O(n) using two-pointer technique.

def mergeSort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    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
    return result + left[i:] + right[j:]

Quick Select (Kth Largest/Smallest)

Quick select finds the kth smallest element in O(n) average time using the partition step from quicksort. Partition around a pivot: elements smaller than pivot go left, larger go right. If the pivot lands at index k-1, it is the answer. If pivot index k-1, recurse on the left half. Unlike quicksort, only one side is recursed — average O(n) time (O(n²) worst case with bad pivot selection, mitigated by random pivot).

import random

def findKthSmallest(nums, k):
    def partition(left, right):
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        pivot = nums[right]
        store = left
        for i in range(left, right):
            if nums[i] <= pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[right] = nums[right], nums[store]
        return store

    left, right = 0, len(nums) - 1
    while left <= right:
        pivot_pos = partition(left, right)
        if pivot_pos == k - 1:
            return nums[pivot_pos]
        elif pivot_pos < k - 1:
            left = pivot_pos + 1
        else:
            right = pivot_pos - 1

Master Theorem

The Master Theorem solves recurrences of the form T(n) = a·T(n/b) + f(n), where a ≥ 1 subproblems of size n/b with combine cost f(n).

Let c = log_b(a) (critical exponent). Compare f(n) to n^c:

  • Case 1: f(n) = O(n^(c-ε)) for some ε > 0 — combining is cheap, subproblems dominate. T(n) = Θ(n^c). Example: binary search T(n) = T(n/2) + O(1) → a=1, b=2, c=0, f(n)=O(1)=O(n^0) → T(n) = Θ(log n).
  • Case 2: f(n) = Θ(n^c) — combining and subproblems are equal. T(n) = Θ(n^c × log n). Example: merge sort T(n) = 2T(n/2) + O(n) → a=2, b=2, c=1, f(n)=O(n)=O(n^1) → T(n) = Θ(n log n).
  • Case 3: f(n) = Ω(n^(c+ε)) — combining dominates. T(n) = Θ(f(n)). Example: if T(n) = T(n/2) + O(n) → a=1, b=2, c=0, f(n)=O(n)=Ω(n^(0+1)) → T(n) = Θ(n).

Binary Search (Divide and Conquer)

Binary search is divide and conquer on a sorted array: check the midpoint, recurse on the half that could contain the answer. T(n) = T(n/2) + O(1) = O(log n). The recursive formulation is pedagogically useful; the iterative implementation avoids stack overhead.

Closest Pair of Points

Finding the closest pair among n points: brute force is O(n²). Divide and conquer: sort by x-coordinate. Divide at midpoint. Recursively find closest pair in each half (distances d_left, d_right). Set d = min(d_left, d_right). The tricky part: check pairs straddling the divide — consider only points within distance d of the dividing line (the “strip”). Points in the strip are sorted by y-coordinate; for each point, only the next 7 points in y-order need to be checked (geometric proof). Total time O(n log n).

Fast Exponentiation (Repeated Squaring)

Compute x^n in O(log n) by: x^n = (x^(n/2))^2 if n is even; x × x^(n-1) if n is odd. This reduces the problem size by half each step. Used for modular exponentiation in cryptography (RSA key generation) and computing Fibonacci in O(log n) via matrix exponentiation.

Interview Problems Using Divide and Conquer

  • LC 23 — Merge K Sorted Lists: divide lists into pairs, merge pairs recursively. O(n log k).
  • LC 148 — Sort List: merge sort on linked list. O(n log n) time, O(log n) stack space.
  • LC 215 — Kth Largest Element: quick select. O(n) average.
  • LC 53 — Maximum Subarray: divide and conquer finds max subarray crossing the midpoint; O(n log n) — though Kadane’s algorithm is O(n) and preferred.
  • LC 169 — Majority Element: Boyer-Moore voting algorithm (O(n)) or divide and conquer (find majority in each half, then verify).
  • LC 315 — Count of Smaller Numbers After Self: merge sort with inversion counting.

  • Coinbase Interview Guide
  • Atlassian Interview Guide
  • LinkedIn Interview Guide
  • Uber Interview Guide
  • Apple Interview Guide

    • Companies That Ask This

    🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture

    Scroll to Top