Sorting & Binary Search: The Algorithms You Use Without Knowing It

The Hidden Presence of Sorting

When a problem says "find all pairs that sum to a target," it doesn't say "sort the array first." When a problem says "merge these overlapping intervals," it doesn't say "sort by start time." When a problem says "find the minimum time to complete all tasks," it doesn't say "use a greedy approach on a sorted list."

But the optimal solution to all three problems starts with sorting. Candidates who don't recognize this reach for nested loops and end up with O(n²). Candidates who do recognize it start with nums.sort() and build the rest in O(n) — total: O(n log n).

That's the pattern this post is about. Not just how sorting algorithms work, but when sorting unlocks a problem entirely, and how binary search extends far beyond "find an element in a sorted array" into one of the most powerful problem-solving techniques in the interview toolkit.

Part 1: Sorting Algorithms

Why Understand Sorting If Python Has sorted()?

Two reasons. First, interviewers ask you to implement sorting algorithms — merge sort and quick sort especially — to test whether you understand divide and conquer and recursion. Second, knowing the properties of different sorting algorithms tells you which one to reach for in edge cases: stability, in-place constraint, nearly-sorted input, small value range.

The Sorting Landscape

The interviewer's favorites: Merge sort (clean recursion, stable, guaranteed), quick sort (in-place, fast in practice, pivot strategy discussion), and counting sort (linear time when range is bounded).

Merge Sort — The Template

Merge sort is the cleanest divide-and-conquer implementation. It's also the sorting algorithm used for linked lists (because linked lists don't support random access, making quick sort impractical).

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[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]:    # <= ensures stability
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

Complexity: T(n) = 2T(n/2) + O(n) → O(n log n) by Master Theorem. Space: O(n) for the merge step.

The counting inversions trick: During merge sort, whenever you take an element from the right half before the right half is exhausted — that element is "inverted" with every remaining element in the left half. This lets you count inversions in O(n log n) as a byproduct of sorting.

def count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left,  left_inv  = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])

    merged = []
    inversions = left_inv + right_inv
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inversions += len(left) - i    # all remaining left elements are inverted

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

Quick Sort — The Template

Quick sort is faster than merge sort in practice due to better cache behavior and lower constant factors. The key design decision is pivot selection.

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)

def partition(arr, low, high):
    # Median-of-three pivot: reduces worst-case probability
    mid = (low + high) // 2
    if arr[mid] < arr[low]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[high] < arr[low]:
        arr[low], arr[high] = arr[high], arr[low]
    if arr[mid] < arr[high]:
        arr[mid], arr[high] = arr[high], arr[mid]
    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

The worst case: O(n²) occurs when every partition is maximally unbalanced — the pivot is always the smallest or largest element. This happens on already-sorted input with a naive last-element pivot. Median-of-three or random pivot selection makes this extremely unlikely.

Quick Sort vs Merge Sort in interviews:

• Need guaranteed O(n log n)? → Merge Sort

• Need in-place sorting? → Quick Sort

• Sorting a linked list? → Merge Sort (random access not available)

• Discussing "what could go wrong"? → Quick Sort (pivot, worst case)

Counting Sort — Linear Time

When values are integers in a known bounded range [0, k], counting sort beats any comparison-based sort:

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1

    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    return result

# Stable counting sort (preserves relative order of equal elements)
def counting_sort_stable(arr, max_val):
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1

    # Prefix sum: count[i] = number of elements <= i
    for i in range(1, max_val + 1):
        count[i] += count[i-1]

    result = [0] * len(arr)
    for num in reversed(arr):     # reversed for stability
        count[num] -= 1
        result[count[num]] = num
    return result

When to reach for counting sort: The problem mentions values in a small range (0–26 for letters, 0–9 for digits, 0–100 for ages, etc.), and you need O(n) instead of O(n log n).

Sorting as a Problem-Solving Unlock

These are the three most common patterns where sorting transforms an intractable problem into a tractable one:

Pattern A — Sort then Two Pointers: For finding pairs/triplets with a target sum, sorting allows two pointers to find pairs in O(n) instead of O(n²) hash map lookups.

# Without sort: O(n²)
def two_sum_naive(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False

# With sort + two pointers: O(n log n)
def two_sum_sorted(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:   return True
        elif s < target:  left += 1
        else:             right -= 1
    return False

Pattern B — Sort then Greedy: Interval problems become tractable after sorting by start or end time. The greedy choice (take earliest-ending interval) is only meaningful on a sorted list.

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])   # sort by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])   # sort by start
    import heapq
    heap = []    # min-heap of end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse a room
        else:
            heapq.heappush(heap, end)     # need a new room
    return len(heap)

Pattern C — Sort then Binary Search: After sorting, every search becomes O(log n) instead of O(n). Useful when you need to find elements or boundaries repeatedly after a one-time sort.

def search_insert_position(nums, target):
    nums.sort()    # one-time O(n log n)
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Part 2: Binary Search

Beyond "Find an Element in a Sorted Array"

Most candidates know binary search for its basic use case. The real power of binary search is its application to the answer space — a technique that solves an entirely different class of problems.

The core idea: if a function f(x) is monotonic (always true for x ≥ threshold, always false below), binary search can find that threshold in O(log(range)) time.

Answer space binary search:
  f(x) = False  False  False  True  True  True  True
                              ↑
                        Find this threshold

Template: Classic Binary Search

def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2   # avoids integer overflow

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

The off-by-one minefield. Four variants — memorize the difference:

# Find leftmost index where nums[mid] >= target
def lower_bound(nums, target):
    left, right = 0, len(nums)           # right = len(nums), not len-1
    while left < right:                  # strict <, not <=
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid                  # don't exclude mid
    return left                          # left == right at termination

# Find leftmost index where nums[mid] > target
def upper_bound(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] <= target:          # only difference: <= vs <
            left = mid + 1
        else:
            right = mid
    return left

# In Python, use bisect module:
import bisect
bisect.bisect_left(nums, target)   # == lower_bound
bisect.bisect_right(nums, target)  # == upper_bound

Binary Search on Answer Space

This is the technique that unlocks Hard problems. When:

• You're asked for a minimum/maximum value satisfying some condition

• The condition is monotonic (if x works, x+1 also works — or vice versa)

• The answer lives in a known range

...then binary search on the answer.

Template:

def binary_search_answer(lo, hi, condition):
    """
    Find the minimum value in [lo, hi] for which condition is True.
    Assumes condition is: False False ... False True True ... True
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid          # mid might be the answer, don't exclude
        else:
            lo = mid + 1      # mid definitely not the answer
    return lo                 # lo == hi == the threshold

Example 1 — Koko Eating Bananas:

def min_eating_speed(piles, h):
    """
    Find minimum eating speed k such that Koko can eat all bananas in h hours.
    Monotonic: if speed k works, speed k+1 also works.
    """
    def can_finish(speed):
        hours = sum((pile + speed - 1) // speed for pile in piles)  # ceil division
        return hours <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Example 2 — Capacity to Ship Packages:

def ship_within_days(weights, days):
    """
    Find minimum ship capacity such that all packages ship within 'days' days.
    """
    def can_ship(capacity):
        current_load, days_needed = 0, 1
        for w in weights:
            if current_load + w > capacity:
                days_needed += 1
                current_load = 0
            current_load += w
        return days_needed <= days

    lo = max(weights)       # minimum: must fit heaviest single package
    hi = sum(weights)       # maximum: ship everything in one day
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Example 3 — Find Peak Element:

def find_peak(nums):
    """
    A peak element is greater than its neighbors.
    Find any peak in O(log n).
    """
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid        # peak is at mid or to the left
        else:
            left = mid + 1     # peak is to the right
    return left

Binary Search on Rotated Arrays

A classic interview variant — the array was sorted but then rotated:

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is sorted
        if nums[left] <= nums[mid]:    # left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1       # target in sorted left half
            else:
                left = mid + 1        # target in right half
        else:                          # right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1        # target in sorted right half
            else:
                right = mid - 1       # target in left half

    return -1

The key insight: In a rotated sorted array, at least one half is always sorted. Identify which half is sorted, check if the target falls within it, and recurse on the correct side.

The Binary Search Decision Framework

Need to SEARCH for a value?
         │
         ▼
Is input sorted (or can be sorted with acceptable cost)?
  ├─ Yes, find exact element → Classic Binary Search
  ├─ Yes, find leftmost position → lower_bound / bisect_left
  ├─ Yes, find rightmost position → upper_bound / bisect_right
  └─ Sorted but rotated → Rotated Array Binary Search
         │
         ▼
Is there a MONOTONIC condition over a known range?
  └─ Yes → Binary Search on Answer Space
     Ask: "If X works, does X+1 also work?"
     If yes → search for minimum X where condition is True
     If no (inverse monotonic) → search for maximum X
         │
         ▼
Is the array NOT sorted and binary search seems wrong?
  └─ "Find peak element" type → still binary search!
     At each step, move toward the direction of increase.

Complexity Summary

where f is the cost of evaluating the condition once.

The 10 Must-Know Problems

Work through 1–3 first (the fundamentals), then 4–6 (sorted array variants), then 7–8 (answer space — the hardest conceptual jump), then 9–10 (where sorting unlocks the solution).

Bottom Line

Sorting is not a topic — it's a reflex. When you see a problem involving pairs, intervals, ordering, or repeated searches, your first thought should be: "Does sorting this input make the rest of the problem easier?" The answer is yes more often than any other single technique.

Binary search on answer space is the most underused technique in the interview toolkit. Most candidates use binary search only on sorted arrays. The moment you internalize "any monotonic condition over a range can be binary searched," your ability to solve Hard problems jumps significantly.

The pattern is always the same: define the condition, verify it's monotonic, set the search boundaries, apply the template. The condition changes per problem. The template never does.

🧭 What's Next in Chapter 3

• Post 11: Recursion & Backtracking — every recursive solution is secretly a tree traversal; master the backtracking template, pruning strategies, and the 4 problem types that appear in every interview