Divide and Conquer: Code Templates in 6 Languages

Coding Patterns - Guide to 30 Core Algorithm Patterns

Divide and Conquer: Complete Guide with Examples

If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template follows the same skeleton: split the input, solve the pieces recursively, and combine the results.

Main Template: Merge Sort

Merge sort is the most common divide and conquer implementation interviewers ask you to write. It splits the array into halves, sorts each half, and merges the sorted halves back together. The merge step is what makes the whole thing work, so pay attention to it.

Use this for Sort an Array .

function mergeSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return; // base case: range is empty or one element

    const mid = Math.floor((left + right) / 2);
    // Split: both halves must stay disjoint and cover the full range
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Combine: the halves are sorted, now merge them
    merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
    // Copy both halves so the merge can write over the original
    // range without losing values it still has to compare
    const n1 = mid - left + 1;
    const n2 = right - mid;
    const leftArr = new Array(n1);
    const rightArr = new Array(n2);

    for (let i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (let j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

    let i = 0, j = 0, k = left;
    // Place the smaller current head of each half back into the array
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
        else arr[k++] = rightArr[j++];
    }
    // One half runs out first; the rest of the other is already in order
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}

def merge_sort(arr: List[int], left: int = 0, right: int = None) -> None:
    if right is None:
        right = len(arr) - 1

    if left >= right:
        return  # base case: nothing left to sort

    mid = (left + right) // 2
    # Split: each element belongs to exactly one half
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)

    # Combine: both halves are sorted, merge them back
    merge(arr, left, mid, right)


def merge(arr: List[int], left: int, mid: int, right: int) -> None:
    # Snapshot the halves first, otherwise the merge writes would
    # overwrite values that still need to be compared
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]

    i = j = 0
    k = left
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1

    # The trailing elements of the longer half are already in place
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1
    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return; // base case: range is empty or one element

    int mid = left + (right - left) / 2;
    // Split: halves are disjoint and together cover the full range
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Combine: both halves are sorted, merge them back
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    // Copy both halves before merging so writes do not clobber
    // values the merge still needs to read
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    // Write the smaller current head of each half back into the array
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
        else arr[k++] = rightArr[j++];
    }
    // One half empties first, the rest of the other is already ordered
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return; // base case: range is empty or one element

    int mid = left + (right - left) / 2;
    // Split: each element lands in exactly one half
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Combine: halves are sorted, merge them back into place
    merge(arr, left, mid, right);
}

void merge(vector<int>& arr, int left, int mid, int right) {
    // Snapshot both halves, otherwise writes would destroy
    // values the merge still has to compare
    vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    size_t i = 0, j = 0, k = left;
    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) arr[k++] = leftArr[i++];
        else arr[k++] = rightArr[j++];
    }
    // One half runs out first; copy the remainder of the other
    while (i < leftArr.size()) arr[k++] = leftArr[i++];
    while (j < rightArr.size()) arr[k++] = rightArr[j++];
}

func mergeSort(arr []int, left, right int) {
    if left >= right {
        return // base case: range is empty or one element
    }

    mid := left + (right-left)/2
    // Split: halves are disjoint and cover the whole range
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)

    // Combine: both halves are sorted, merge them back
    merge(arr, left, mid, right)
}

func merge(arr []int, left, mid, right int) {
    // Copy the halves first; the merge writes back into the
    // original range and would clobber values still being compared
    leftArr := make([]int, mid-left+1)
    rightArr := make([]int, right-mid)
    copy(leftArr, arr[left:mid+1])
    copy(rightArr, arr[mid+1:right+1])

    i, j, k := 0, 0, left
    for i < len(leftArr) && j < len(rightArr) {
        if leftArr[i] <= rightArr[j] {
            arr[k] = leftArr[i]
            i++
        } else {
            arr[k] = rightArr[j]
            j++
        }
        k++
    }
    // The leftover tail of one half is already in order
    for i < len(leftArr) {
        arr[k] = leftArr[i]
        i++
        k++
    }
    for j < len(rightArr) {
        arr[k] = rightArr[j]
        j++
        k++
    }
}

def merge_sort(arr, left = 0, right = arr.length - 1)
    return if left >= right  # base case: empty or single element

    mid = (left + right) / 2
    # Split: the halves never overlap and cover the full range
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)

    # Combine: halves are sorted, merge them back
    merge(arr, left, mid, right)
end

def merge(arr, left, mid, right)
    # Snapshot the halves so merging in place does not
    # overwrite values the merge still needs to compare
    left_arr = arr[left..mid]
    right_arr = arr[mid + 1..right]

    i = 0
    j = 0
    k = left
    while i < left_arr.length && j < right_arr.length
        if left_arr[i] <= right_arr[j]
            arr[k] = left_arr[i]
            i += 1
        else
            arr[k] = right_arr[j]
            j += 1
        end
        k += 1
    end
    # The rest of the longer half is already in position
    while i < left_arr.length
        arr[k] = left_arr[i]
        i += 1
        k += 1
    end
    while j < right_arr.length
        arr[k] = right_arr[j]
        j += 1
        k += 1
    end
end

Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

left and right: the range of the array the current call owns. Every recursive call narrows this range until it hits the base case.
mid: the boundary between the two halves, computed as the midpoint of left and right. Everything at or before mid belongs to the first half.
leftArr and rightArr (merge): temporary copies of the two sorted halves, needed so the merge can write over the original range without losing values it still has to read.
i, j, and k (merge): the read cursors for the left and right copies plus the write cursor for the original array. i and j advance when their element is placed, k advances on every write.

Visual Mechanism

    stateDiagram-v2
    [*] --> Split: sort both halves recursively
    Split --> Merge: both halves sorted
    Merge --> Done: write sorted merge back
    Done --> [*]

Critical Sections

The base case left >= right stops the recursion when the range has one element or fewer, and it is what prevents infinite recursion on empty input.

The split is just arithmetic. Because left and mid are inclusive and the second half starts at mid plus one, every element lands in exactly one half, which is why the off-by-one at this line matters.

The merge loop compares the current heads of both halves and writes the smaller one back into the original array. The two trailing loops exist because after one half is exhausted, the remainder of the other half is already in order and can be copied over directly.

The temporary arrays are not an optimization detail. Without them, writing the smaller element back would overwrite values the merge still needs to compare.

Variations

1. Quick Sort (In-Place Partition)

Quick sort sorts in place instead of merging. It partitions the segment around a pivot so that smaller elements land on the left and larger ones on the right, then recurses on both sides. The partition function below also powers quickselect in the next variation.

function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low >= high) return;

    const pivotIndex = partition(arr, low, high);
    // The pivot is already in its final position, so recurse
    // on the sides around it
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

function partition(arr, low, high) {
    const pivot = arr[high]; // rightmost element as the pivot
    let i = low;
    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            // Move elements smaller than the pivot left,
            // everything else is pushed right implicitly
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    // The pivot lands between the two groups
    [arr[i], arr[high]] = [arr[high], arr[i]];
    return i;
}

def quick_sort(arr: List[int], low: int = 0, high: int = None) -> None:
    if high is None:
        high = len(arr) - 1

    if low >= high:
        return

    pivot_index = partition(arr, low, high)
    # The pivot sits in its final spot, only the sides need sorting
    quick_sort(arr, low, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, high)


def partition(arr: List[int], low: int, high: int) -> int:
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            # Everything below i is smaller than the pivot,
            # everything from i to j is not yet placed
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

public void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;

    int pivotIndex = partition(arr, low, high);
    // The pivot is final; sort the two sides independently
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

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

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) return;

    int pivotIndex = partition(arr, low, high);
    // Pivot is settled, recurse on the two sides
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[i++], arr[j]);
        }
    }
    swap(arr[i], arr[high]);
    return i;
}

func quickSort(arr []int, low, high int) {
    if low >= high {
        return
    }

    pivotIndex := partition(arr, low, high)
    // The pivot never moves again, sort the sides around it
    quickSort(arr, low, pivotIndex-1)
    quickSort(arr, pivotIndex+1, high)
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            arr[i], arr[j] = arr[j], arr[i]
            i++
        }
    }
    arr[i], arr[high] = arr[high], arr[i]
    return i
}

def quick_sort(arr, low = 0, high = arr.length - 1)
    return if low >= high

    pivot_index = partition(arr, low, high)
    # The pivot is in its final position, sort both sides
    quick_sort(arr, low, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, high)
end

def partition(arr, low, high)
    pivot = arr[high]
    i = low
    (low...high).each do |j|
        if arr[j] < pivot
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
        end
    end
    arr[i], arr[high] = arr[high], arr[i]
    i
end

Visual

    graph TD
    A["Array segment"] --> B["Pick pivot (last element)"]
    B --> C["Swap smaller elements left"]
    C --> D["Pivot to its final position"]
    D --> E["Recurse on both sides"]

2. Quickselect (Kth Largest Element)

Quickselect borrows the partition step but recurses into only one side, the side that contains the target index. That pruning is what drops the average cost to linear. For the kth largest element, the target index in sorted order is the array length minus k.

Use this for Kth Largest Element in an Array .

function findKthLargest(nums, k) {
    // The kth largest value sits at index n-k once the array is sorted
    const target = nums.length - k;
    let low = 0, high = nums.length - 1;

    while (low <= high) {
        const pivotIndex = partition(nums, low, high);
        // Follow only the branch that contains the target index,
        // which is why quickselect averages O(N) instead of O(N log N)
        if (pivotIndex === target) return nums[pivotIndex];
        if (pivotIndex < target) low = pivotIndex + 1;
        else high = pivotIndex - 1;
    }
}

function partition(nums, low, high) {
    const pivot = nums[high];
    let i = low;
    for (let j = low; j < high; j++) {
        if (nums[j] < pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }
    [nums[i], nums[high]] = [nums[high], nums[i]];
    return i;
}

def find_kth_largest(nums: List[int], k: int) -> int:
    target = len(nums) - k

    def partition(low: int, high: int) -> int:
        pivot = nums[high]
        i = low
        for j in range(low, high):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[high] = nums[high], nums[i]
        return i

    low, high = 0, len(nums) - 1
    while low <= high:
        p = partition(low, high)
        # Discard the half that cannot hold the target, then repeat
        if p == target:
            return nums[p]
        if p < target:
            low = p + 1
        else:
            high = p - 1

public int findKthLargest(int[] nums, int k) {
    int target = nums.length - k;
    int low = 0, high = nums.length - 1;

    while (low <= high) {
        int pivotIndex = partition(nums, low, high);
        if (pivotIndex == target) return nums[pivotIndex];
        // Only the half containing the target index is searched
        if (pivotIndex < target) low = pivotIndex + 1;
        else high = pivotIndex - 1;
    }
    return -1;
}

private int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (nums[j] < pivot) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
        }
    }
    int temp = nums[i];
    nums[i] = nums[high];
    nums[high] = temp;
    return i;
}

int findKthLargest(vector<int>& nums, int k) {
    int target = nums.size() - k;
    int low = 0, high = nums.size() - 1;

    while (low <= high) {
        int pivotIndex = partition(nums, low, high);
        if (pivotIndex == target) return nums[pivotIndex];
        if (pivotIndex < target) low = pivotIndex + 1;
        else high = pivotIndex - 1;
    }
    return -1;
}

int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (nums[j] < pivot) swap(nums[i++], nums[j]);
    }
    swap(nums[i], nums[high]);
    return i;
}

func findKthLargest(nums []int, k int) int {
    target := len(nums) - k
    low, high := 0, len(nums)-1

    for low <= high {
        pivotIndex := partition(nums, low, high)
        if pivotIndex == target {
            return nums[pivotIndex]
        }
        // Search only the side that could contain the target
        if pivotIndex < target {
            low = pivotIndex + 1
        } else {
            high = pivotIndex - 1
        }
    }
    return -1
}

func partition(nums []int, low, high int) int {
    pivot := nums[high]
    i := low
    for j := low; j < high; j++ {
        if nums[j] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
    nums[i], nums[high] = nums[high], nums[i]
    return i
}

def find_kth_largest(nums, k)
    target = nums.length - k
    low = 0
    high = nums.length - 1

    while low <= high
        pivot_index = partition(nums, low, high)
        return nums[pivot_index] if pivot_index == target

        if pivot_index < target
            low = pivot_index + 1
        else
            high = pivot_index - 1
        end
    end
end

def partition(nums, low, high)
    pivot = nums[high]
    i = low
    (low...high).each do |j|
        if nums[j] < pivot
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
        end
    end
    nums[i], nums[high] = nums[high], nums[i]
    i
end

Visual

    graph TD
    A["Partition around pivot"] --> B{"Pivot index == target?"}
    B -->|Yes| C["Return pivot value"]
    B -->|No| D{"Pivot index < target?"}
    D -->|Yes| E["Search right half"]
    D -->|No| F["Search left half"]
    E --> A
    F --> A

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .