Divide Conquer Merge Sort, Max Subarray: Tutorial, Examples, FAQs & Interview Tips

Divide and Conquer

Divide and Conquer is an algorithm design technique in which a problem is broken into smaller subproblems of the same type, each subproblem is solved separately, and the smaller solutions are combined to form the final answer.

This technique is very powerful because many difficult problems become much easier when they are split into smaller parts. It is widely used in searching, sorting, matrix operations, tree algorithms, and computational geometry.

Core Idea

A divide-and-conquer algorithm usually follows three steps:

Divide: Split the original problem into smaller subproblems.
Conquer: Solve the subproblems recursively.
Combine: Merge the smaller solutions into the final result.

Main insight: The method works best when the subproblems are mostly independent and resemble the original problem in structure.

General Structure

General Divide and Conquer Pattern

int solve(Problem input) {
    if (small enough problem) {
        return direct solution;
    }

    Problem leftPart = divide(input);
    Problem rightPart = divide(input);

    int leftAnswer = solve(leftPart);
    int rightAnswer = solve(rightPart);

    return combine(leftAnswer, rightAnswer);
}

The base case handles very small inputs directly, while larger inputs are solved using recursive decomposition.

When to Use Divide and Conquer

This strategy is a good fit when:

The problem can be split into smaller subproblems of the same form.
The subproblems are independent or mostly independent.
The recursive breakdown reduces problem size significantly.
The combine step is efficient enough to justify the split.

If subproblems overlap heavily, then dynamic programming is often a better choice.

Common Divide and Conquer Algorithms

Algorithm	Divide Step	Conquer Step	Combine Step	Typical Complexity
Binary Search	Split the search interval into two halves	Continue in one half	No explicit combine step	O(log n)
Merge Sort	Split array into two halves	Sort each half recursively	Merge sorted halves	O(n log n)
Quick Sort	Partition around a pivot	Sort left and right partitions	No major merge step	O(n log n) average
Maximum Subarray	Split array around middle	Find best left and right subarrays	Check crossing subarray	O(n log n)
Strassen Matrix Multiplication	Split matrices into blocks	Recursive multiplication of blocks	Add and subtract block results	About O(n^2.81)

Example 1: Binary Search

Binary Search is one of the simplest divide-and-conquer algorithms. At every step, the search interval is cut into two halves, and only one half is explored.

Binary Search

public class BinarySearch {

    static int search(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        }

        if (target < arr[mid]) {
            return search(arr, low, mid - 1, target);
        }

        return search(arr, mid + 1, high, target);
    }
}

Recurrence: T(n) = T(n / 2) + O(1), so the time complexity is O(log n).

Example 2: Merge Sort

Merge Sort is the classic divide-and-conquer sorting algorithm. It repeatedly splits the array into halves, sorts each half recursively, and then merges the two sorted halves.

Merge Sort

import java.util.Arrays;

public class MergeSort {

    static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int[] leftPart = Arrays.copyOfRange(arr, left, mid + 1);
        int[] rightPart = Arrays.copyOfRange(arr, mid + 1, right + 1);

        int i = 0;
        int j = 0;
        int k = left;

        while (i < leftPart.length && j < rightPart.length) {
            if (leftPart[i] <= rightPart[j]) {
                arr[k++] = leftPart[i++];
            } else {
                arr[k++] = rightPart[j++];
            }
        }

        while (i < leftPart.length) {
            arr[k++] = leftPart[i++];
        }

        while (j < rightPart.length) {
            arr[k++] = rightPart[j++];
        }
    }
}

Recurrence: T(n) = 2T(n / 2) + O(n). By the Master Theorem, the complexity becomes O(n log n).

Example 3: Quick Sort

Quick Sort also uses divide and conquer. It chooses a pivot, partitions the array into smaller and larger elements, and recursively sorts the partitions.

Quick Sort

public class QuickSort {

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}

Quick Sort has O(n log n) average time, but its worst case can degrade to O(n^2) if partitions are highly unbalanced.

Example 4: Maximum Subarray

The maximum subarray problem asks for the contiguous subarray with the largest sum. The divide-and-conquer solution splits the array into left and right halves and also considers a subarray crossing the midpoint.

Maximum Subarray

public class MaxSubarray {

    static int maxCrossing(int[] arr, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            leftSum = Math.max(leftSum, sum);
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;

        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }

    static int maxSubarray(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }

        int mid = (left + right) / 2;

        return Math.max(
            Math.max(maxSubarray(arr, left, mid), maxSubarray(arr, mid + 1, right)),
            maxCrossing(arr, left, mid, right)
        );
    }
}

This divide-and-conquer approach runs in O(n log n), although Kadane's algorithm solves the same problem in O(n).

Advantages of Divide and Conquer

It provides a clean and systematic problem-solving strategy.
Many divide-and-conquer algorithms are very efficient.
Independent subproblems can often be solved in parallel.
It is a natural fit for recursive thinking.

Limitations of Divide and Conquer

Recursive calls add function-call overhead.
Some algorithms need extra memory for combining results.
It is not ideal when subproblems overlap significantly.
Performance may degrade if the divide step becomes unbalanced, as in worst-case Quick Sort.

Divide and Conquer vs Dynamic Programming

Aspect	Divide and Conquer	Dynamic Programming
Subproblems	Usually independent	Usually overlapping
Reuse of solutions	Generally not required	Required through memoization or tabulation
Examples	Merge Sort, Quick Sort, Binary Search	Knapsack, Fibonacci DP, LCS

Key Takeaways

Divide and Conquer works by dividing a problem, solving smaller parts, and combining the results.
It is most useful when the subproblems are similar and largely independent.
Binary Search, Merge Sort, Quick Sort, and Maximum Subarray are classic examples.
Recurrence relations are commonly used to analyze divide-and-conquer complexity.
The technique is elegant and powerful, but it may involve recursion overhead and extra memory.

Previous Next