Divide and Conquer

def divide_and_conquer(problem):
    # Base case
    if is_trivial(problem):
        return solve_directly(problem)
    
    # Divide
    subproblems = split(problem)
    
    # Conquer (recursive calls)
    sub_results = [divide_and_conquer(sub) for sub in subproblems]
    
    # Combine
    return merge(sub_results)

def merge_sort(arr):
    """O(n log n) stable sort"""
    if len(arr) <= 1:
        return arr
    
    # Divide
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # Combine (merge)
    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
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def quick_sort(arr, low, high):
    """O(n log n) average, in-place sort"""
    if low < high:
        # Partition and get pivot position
        pivot_idx = partition(arr, low, high)
        
        # Conquer
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)

def partition(arr, low, high):
    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

def max_subarray(nums, left, right):
    """Find max subarray sum using D and C"""
    if left == right:
        return nums[left]
    
    mid = (left + right) // 2
    
    # Max in left half
    left_max = max_subarray(nums, left, mid)
    # Max in right half
    right_max = max_subarray(nums, mid + 1, right)
    # Max crossing middle
    cross_max = max_crossing_sum(nums, left, mid, right)
    
    return max(left_max, right_max, cross_max)

def max_crossing_sum(nums, left, mid, right):
    # Max sum ending at mid
    left_sum = float('-inf')
    total = 0
    for i in range(mid, left - 1, -1):
        total += nums[i]
        left_sum = max(left_sum, total)
    
    # Max sum starting after mid
    right_sum = float('-inf')
    total = 0
    for i in range(mid + 1, right + 1):
        total += nums[i]
        right_sum = max(right_sum, total)
    
    return left_sum + right_sum

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def max_depth(root):
    """D and C on tree structure"""
    if not root:
        return 0
    
    # Divide and Conquer
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    # Combine
    return 1 + max(left_depth, right_depth)