The Algorithms - Python Python TheAlgorithms/Python

Divide and Conquer Algorithms in TheAlgorithms/Python

Six algorithms that split a problem in half, solve each half independently, and combine the results: from sorting to matrix multiplication to geometry.

6 stops ~12 min Verified 2026-05-05

What you will learn

How divide_and_conquer/mergesort.py uses index pointers to avoid Python list pop overhead
How convex_hull_recursive divides points by their sign relative to the leftmost-rightmost line
How closest_pair_of_points_sqr splits on the x-coordinate midpoint and checks a cross-strip for pairs spanning the divide
How Strassen's algorithm reduces a matrix multiply from 8 recursive calls to 7 by computing intermediate products
How max_subarray splits the array at the midpoint and combines three candidate maximums: left, right, and crossing
How actual_power avoids redundant computation by squaring the half-power result instead of multiplying twice

Prerequisites

Comfort reading recursive Python functions with list slicing
Understanding of what O(n log n) complexity means in terms of recursion depth

1 / 6

Mergesort: three-pointer merge avoids pop() overhead

divide_and_conquer/mergesort.py:4

Three index pointers walk the two sorted halves and fill a pre-allocated output array, avoiding the O(n) cost of list.pop(0) used in sorts/merge_sort.py.

This file is the divide-and-conquer counterpart to sorts/merge_sort.py. The core difference is in the merge function. The version in sorts/ calls left.pop(0) to remove the front element each step, which is O(n) on Python lists. This version allocates sorted_array upfront as a fixed-length list and uses three integer pointers to walk the halves without mutation. pointer1 and pointer2 track the current read position in each half; index tracks the write position in the output. When the main while loop ends, one half may still have remaining elements; the two trailing while loops drain it. The merge_sort function below uses the integer midpoint formula 0 + (len(array) - 0) // 2, which the comment notes avoids integer overflow in languages with fixed-width integers. For a full tour of this algorithm, see the deeper tour.

Key takeaway

Using three index pointers and a pre-allocated output array makes merge run in O(n) writes without the O(n) penalty of list.pop(0).

def merge(left_half: list, right_half: list) -> list:
    """Helper function for mergesort.

    >>> left_half = [-2]
    >>> right_half = [-1]
    >>> merge(left_half, right_half)
    [-2, -1]

    >>> left_half = [1,2,3]
    >>> right_half = [4,5,6]
    >>> merge(left_half, right_half)
    [1, 2, 3, 4, 5, 6]

    >>> left_half = [-2]
    >>> right_half = [-1]
    >>> merge(left_half, right_half)
    [-2, -1]

    >>> left_half = [12, 15]
    >>> right_half = [13, 14]
    >>> merge(left_half, right_half)
    [12, 13, 14, 15]

    >>> left_half = []
    >>> right_half = []
    >>> merge(left_half, right_half)
    []
    """
    sorted_array = [None] * (len(right_half) + len(left_half))

    pointer1 = 0  # pointer to current index for left Half
    pointer2 = 0  # pointer to current index for the right Half
    index = 0  # pointer to current index for the sorted array Half

    while pointer1 < len(left_half) and pointer2 < len(right_half):
        if left_half[pointer1] < right_half[pointer2]:
            sorted_array[index] = left_half[pointer1]
            pointer1 += 1
            index += 1
        else:
            sorted_array[index] = right_half[pointer2]
            pointer2 += 1
            index += 1
    while pointer1 < len(left_half):
        sorted_array[index] = left_half[pointer1]
        pointer1 += 1
        index += 1

    while pointer2 < len(right_half):
        sorted_array[index] = right_half[pointer2]
        pointer2 += 1
        index += 1

    return sorted_array

2 / 6

Convex hull: divide points by sign of the cross product, recurse on each half

divide_and_conquer/convex_hull.py:329

The cross product sign (_det) tells which side of the anchor line a point is on; points above go to the upper sub-problem, points below to the lower sub-problem.

The convex hull problem asks for the smallest convex polygon enclosing a set of 2D points. The brute-force version in the same file runs in O(n cubed). This divide-and-conquer version runs in O(n log n) by partitioning the problem using two geometric anchors. Because the input is sorted by x-coordinate, points[0] is the leftmost and points[n-1] is the rightmost; both are guaranteed to be on the hull. The helper _det(a, b, c) computes the signed area of the triangle formed by three points, which equals the cross product of vectors ab and ac. A positive value means point c is above the line from a to b; negative means below. Points with a zero determinant lie on the line and cannot be hull vertices. The two resulting sub-lists are passed to _construct_hull, which recursively finds the hull points furthest from the anchor line.

Key takeaway

The cross product sign partitions points into upper and lower hulls; the extreme points are guaranteed hull members and serve as anchors for both recursive sub-problems.

    n = len(points)

    # divide all the points into an upper hull and a lower hull
    # the left most point and the right most point are definitely
    # members of the convex hull by definition.
    # use these two anchors to divide all the points into two hulls,
    # an upper hull and a lower hull.

    # all points to the left (above) the line joining the extreme points belong to the
    # upper hull
    # all points to the right (below) the line joining the extreme points below to the
    # lower hull
    # ignore all points on the line joining the extreme points since they cannot be
    # part of the convex hull

    left_most_point = points[0]
    right_most_point = points[n - 1]

    convex_set = {left_most_point, right_most_point}
    upper_hull = []
    lower_hull = []

    for i in range(1, n - 1):
        det = _det(left_most_point, right_most_point, points[i])

        if det > 0:
            upper_hull.append(points[i])
        elif det < 0:
            lower_hull.append(points[i])

3 / 6

Closest pair: recurse on halves, then check a cross-strip for pairs spanning the divide

divide_and_conquer/closest_pair_of_points.py:82

After the recursive minimum is known, a cross-strip filters points within that distance of the midpoint x-coordinate; the strip search handles pairs that span the dividing line.

Finding the closest pair of points naively requires comparing every pair in O(n squared). The divide-and-conquer version reaches O(n log n) by splitting the point set at the x-coordinate midpoint. Each half is solved recursively to find its minimum distance. The minimum of those two distances is closest_pair_dis. However, the true closest pair may straddle the dividing line. To handle that, a cross-strip collects every point whose x-coordinate is within closest_pair_dis of the midpoint. The dis_between_closest_in_strip helper searches this strip, but because the y-sorted order limits the number of comparisons per point, the strip search runs in O(n) despite looking quadratic. The final result is the minimum of the two half-results and the strip result. Note: the file returns squared distances to avoid a square root per comparison; closest_pair_of_points converts the result at the end.

Key takeaway

The cross-strip is the non-obvious part of closest-pair: it filters to points within the current minimum distance of the midpoint, catching pairs that span the divide.

def closest_pair_of_points_sqr(points_sorted_on_x, points_sorted_on_y, points_counts):
    """divide and conquer approach

    Parameters :
    points, points_count (list(tuple(int, int)), int)

    Returns :
    (float):  distance btw closest pair of points

    >>> closest_pair_of_points_sqr([(1, 2), (3, 4)], [(5, 6), (7, 8)], 2)
    8
    """

    # base case
    if points_counts <= 3:
        return dis_between_closest_pair(points_sorted_on_x, points_counts)

    # recursion
    mid = points_counts // 2
    closest_in_left = closest_pair_of_points_sqr(
        points_sorted_on_x, points_sorted_on_y[:mid], mid
    )
    closest_in_right = closest_pair_of_points_sqr(
        points_sorted_on_y, points_sorted_on_y[mid:], points_counts - mid
    )
    closest_pair_dis = min(closest_in_left, closest_in_right)

    """
    cross_strip contains the points, whose Xcoords are at a
    distance(< closest_pair_dis) from mid's Xcoord
    """

    cross_strip = []
    for point in points_sorted_on_x:
        if abs(point[0] - points_sorted_on_x[mid][0]) < closest_pair_dis:
            cross_strip.append(point)

4 / 6

Strassen: 7 recursive products replace the naive 8, reducing the exponent of n

divide_and_conquer/strassen_matrix_multiplication.py:82

Strassen replaces 8 recursive matrix multiplications with 7 by computing auxiliary products from sub-matrix sums and differences.

Standard matrix multiplication of two n-by-n matrices requires 8 recursive multiplications of (n/2)-by-(n/2) sub-matrices, which gives a recurrence of T(n) = 8 T(n/2) + O(n squared) and a solution of O(n cubed). Strassen's algorithm reduces the 8 recursive calls to 7, changing the recurrence to T(n) = 7 T(n/2) + O(n squared), which resolves to approximately O(n to the 2.81). The savings come from computing 7 intermediate products t1 through t7 from sub-matrix additions and subtractions, then assembling the four output quadrants as linear combinations of those products. split_matrix divides each input into four equal quadrants. The base case (line 79-80 above this slice) handles 2-by-2 matrices with direct multiplication. The outer strassen function pads non-power-of-two matrices before calling actual_strassen.

Key takeaway

Seven auxiliary products replace eight recursive calls; the output quadrants are linear combinations of those products, reducing complexity from O(n cubed) to O(n to the 2.81).

    a, b, c, d = split_matrix(matrix_a)
    e, f, g, h = split_matrix(matrix_b)

    t1 = actual_strassen(a, matrix_subtraction(f, h))
    t2 = actual_strassen(matrix_addition(a, b), h)
    t3 = actual_strassen(matrix_addition(c, d), e)
    t4 = actual_strassen(d, matrix_subtraction(g, e))
    t5 = actual_strassen(matrix_addition(a, d), matrix_addition(e, h))
    t6 = actual_strassen(matrix_subtraction(b, d), matrix_addition(g, h))
    t7 = actual_strassen(matrix_subtraction(a, c), matrix_addition(e, f))

    top_left = matrix_addition(matrix_subtraction(matrix_addition(t5, t4), t2), t6)
    top_right = matrix_addition(t1, t2)
    bot_left = matrix_addition(t3, t4)
    bot_right = matrix_subtraction(matrix_subtraction(matrix_addition(t1, t5), t3), t7)

5 / 6

Maximum subarray: split at midpoint, pick the largest of left, right, or crossing

divide_and_conquer/max_subarray.py:19

Three candidates are compared: the maximum subarray entirely in the left half, entirely in the right half, or crossing the midpoint from left to right.

The maximum subarray problem asks for the contiguous subarray with the largest sum. The brute-force approach tries all pairs of start and end indices in O(n squared). This divide-and-conquer solution runs in O(n log n) by observing that the answer is one of three cases: the maximum subarray lies entirely in the left half, entirely in the right half, or straddles the midpoint. The function recurses on both halves for the first two cases. For the third case, max_cross_sum scans leftward from the midpoint accumulating a running sum and scans rightward from mid+1, then combines the two best prefixes. Three if-elif clauses compare all three sums and return the winner with its index bounds. The doctests cover the canonical negative-number example [-2, 1, -3, 4, -1, 2, 1, -5, 4], whose maximum subarray [4, -1, 2, 1] sums to 6.

Key takeaway

Maximum subarray has exactly three candidates: left half, right half, and crossing. The crossing case requires a dedicated helper that scans outward from the midpoint in both directions.

def max_subarray(
    arr: Sequence[float], low: int, high: int
) -> tuple[int | None, int | None, float]:
    """
    Solves the maximum subarray problem using divide and conquer.
    :param arr:     the given array of numbers
    :param low:     the start index
    :param high:    the end index
    :return:        the start index of the maximum subarray, the end index of the
                    maximum subarray, and the maximum subarray sum

    >>> nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    >>> max_subarray(nums, 0, len(nums) - 1)
    (3, 6, 6)
    >>> nums = [2, 8, 9]
    >>> max_subarray(nums, 0, len(nums) - 1)
    (0, 2, 19)
    >>> nums = [0, 0]
    >>> max_subarray(nums, 0, len(nums) - 1)
    (0, 0, 0)
    >>> nums = [-1.0, 0.0, 1.0]
    >>> max_subarray(nums, 0, len(nums) - 1)
    (2, 2, 1.0)
    >>> nums = [-2, -3, -1, -4, -6]
    >>> max_subarray(nums, 0, len(nums) - 1)
    (2, 2, -1)
    >>> max_subarray([], 0, 0)
    (None, None, 0)
    """
    if not arr:
        return None, None, 0
    if low == high:
        return low, high, arr[low]

    mid = (low + high) // 2
    left_low, left_high, left_sum = max_subarray(arr, low, mid)
    right_low, right_high, right_sum = max_subarray(arr, mid + 1, high)
    cross_left, cross_right, cross_sum = max_cross_sum(arr, low, mid, high)
    if left_sum >= right_sum and left_sum >= cross_sum:
        return left_low, left_high, left_sum
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return right_low, right_high, right_sum
    return cross_left, cross_right, cross_sum

6 / 6

Power: square the half-power result to halve the recursive calls

divide_and_conquer/power.py:1

Dividing the exponent by 2 and squaring the result reduces the recursion depth to O(log b), computing a^b with far fewer multiplications than the naive approach.

Computing a to the power b naively requires b multiplications. Divide and conquer reduces this to O(log b) by exploiting the identity: if b is even, then a^b equals (a^(b/2)) squared; if b is odd, then a^b equals a times (a^((b-1)/2)) squared. The function computes half = actual_power(a, b // 2) first, making one recursive call. For even exponents the result is half times half; for odd exponents it is a times half times half. In both cases only one multiplication (or two) is needed after the recursive call returns. The outer power function handles negative exponents by computing 1 / actual_power(a, -b) and returning a float. The doctests confirm: 3^2 is 9, 5^3 is 125, 2^5 is 32, and any base to the power 0 is 1.

Key takeaway

Fast exponentiation computes the half-power once and squares it: one recursive call replaces two, halving the recursion depth each level to achieve O(log b) multiplications.

def actual_power(a: int, b: int) -> int:
    """
    Function using divide and conquer to calculate a^b.
    It only works for integer a,b.

    :param a: The base of the power operation, an integer.
    :param b: The exponent of the power operation, a non-negative integer.
    :return: The result of a^b.

    Examples:
    >>> actual_power(3, 2)
    9
    >>> actual_power(5, 3)
    125
    >>> actual_power(2, 5)
    32
    >>> actual_power(7, 0)
    1
    """
    if b == 0:
        return 1
    half = actual_power(a, b // 2)

    if (b % 2) == 0:
        return half * half
    else:
        return a * half * half

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free