Sorting & Binary Search

Concept

Merge sort splits the array in half, sorts each half and merges: always O(n log n), stable, O(n) extra space.

Quick sort picks a pivot and partitions: O(n log n) average, O(n²) worst case, in place.

Binary search halves a sorted range each step. It also works on any monotonic yes/no condition (“binary search on the answer”).

Complexity

Code (Python)

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

def merge_sort(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    L, R = merge_sort(a[:m]), merge_sort(a[m:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: out.append(L[i]); i += 1
        else: out.append(R[j]); j += 1
    return out + L[i:] + R[j:]

Remember

• Watch off-by-one: lo <= hi vs lo < hi.
• Sorted or monotonic → binary search.
• Know which sorts are stable.