DSA — Divide and Conquer

What is Divide and Conquer?

1. Divide the problem into subproblems
2. Conquer each subproblem recursively
3. Combine the results

Merge Sort (Classic Example)

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]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Quick Sort

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

Binary Search

def binary_search(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

Time Complexity

Algorithm	Complexity
Merge Sort	O(n log n)
Quick Sort	O(n log n) avg
Binary Search	O(log n)

Mini Practice

1. Implement merge sort
2. Implement quick sort
3. Solve maximum subarray
4. Find closest pair of points

Up Next

Continue with Sliding Window — sliding window technique.