Coding Patterns
Divide and Conquer
Code Templates

Code Templates

Use these adaptable code templates as starting points for solving divide and conquer problems. Each template includes the core structure with comments explaining the divide, conquer, and combine steps.

Merge Sort

Merge Sort is the classic example of Divide and Conquer. It guarantees $O(N \log N)$ time complexity and is a stable sort.

Time:

O(N log N)
| Space:
O(N)

Code Breakdown 

  graph TD
    Input[Input Array] -->|Divide| Left[Left Half]
    Input -->|Divide| Right[Right Half]
    Left -->|Recurse| SortedLeft[Sorted Left]
    Right -->|Recurse| SortedRight[Sorted Right]
    SortedLeft & SortedRight -->|Conquer: Merge| Output[Sorted Output]

/**
 * Template for merge sort using divide and conquer
 * Use when: Need stable sort, linked lists, external sorting
 * Time: O(n log n), Space: O(n)
 */
function mergeSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return;

    const mid = Math.floor((left + right) / 2);

    // Divide: Sort both halves
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    // Conquer: Merge sorted halves
    merge(arr, left, mid, right);
}

function merge(arr, left, mid, right) {
    const n1 = mid - left + 1;
    const n2 = right - mid;

    // Create temporary arrays
    const leftArr = new Array(n1);
    const rightArr = new Array(n2);

    // Copy data to temp arrays
    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];

    // Merge: Combine sorted arrays
    let i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // Copy remaining elements
    while (i < n1) arr[k++] = leftArr[i++];
    while (j < n2) arr[k++] = rightArr[j++];
}
"""
Template for merge sort using divide and conquer
Use when: Need stable sort, linked lists, external sorting
Time: O(n log n), Space: O(n)
"""
def merge_sort(arr, left=None, right=None):
    if left is None:
        left = 0
    if right is None:
        right = len(arr) - 1

    if left >= right:
        return

    mid = (left + right) // 2

    # Divide: Sort both halves
    merge_sort(arr, left, mid)
    merge_sort(arr, mid + 1, right)

    # Conquer: Merge sorted halves
    merge(arr, left, mid, right)

def merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid

    # Create temporary arrays
    left_arr = arr[left:left + n1]
    right_arr = arr[mid + 1:mid + 1 + n2]

    # Merge: Combine sorted arrays
    i = j = 0
    k = left

    while i < n1 and j < n2:
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1

    # Copy remaining elements
    while i < n1:
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = right_arr[j]
        j += 1
        k += 1
/**
 * Template for merge sort using divide and conquer
 * Use when: Need stable sort, linked lists, external sorting
 * Time: O(n log n), Space: O(n)
 */
public class MergeSort {
    public void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;

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

        // Divide: Sort both halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Conquer: Merge sorted halves
        merge(arr, left, mid, right);
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary arrays
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // Copy data to temp arrays
        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];

        // Merge: Combine sorted arrays
        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        // Copy remaining elements
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
}
/**
 * Template for merge sort using divide and conquer
 * Use when: Need stable sort, linked lists, external sorting
 * Time: O(n log n), Space: O(n)
 */
#include <vector>
using namespace std;

class MergeSort {
public:
    void mergeSort(vector<int>& arr, int left, int right) {
        if (left >= right) return;

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

        // Divide: Sort both halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Conquer: Merge sorted halves
        merge(arr, left, mid, right);
    }

private:
    void merge(vector<int>& arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // Create temporary vectors
        vector<int> leftArr(n1), rightArr(n2);

        // Copy data to temp vectors
        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];

        // Merge: Combine sorted arrays
        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k++] = leftArr[i++];
            } else {
                arr[k++] = rightArr[j++];
            }
        }

        // Copy remaining elements
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }
};
/**
 * Template for merge sort using divide and conquer
 * Use when: Need stable sort, linked lists, external sorting
 * Time: O(n log n), Space: O(n)
 */
func mergeSort(arr []int, left int, right int) {
    if left >= right {
        return
    }

    mid := left + (right-left)/2

    // Divide: Sort both halves
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)

    // Conquer: Merge sorted halves
    merge(arr, left, mid, right)
}

func merge(arr []int, left int, mid int, right int) {
    n1 := mid - left + 1
    n2 := right - mid

    // Create temporary slices
    leftArr := make([]int, n1)
    rightArr := make([]int, n2)

    // Copy data to temp slices
    for i := 0; i < n1; i++ {
        leftArr[i] = arr[left+i]
    }
    for j := 0; j < n2; j++ {
        rightArr[j] = arr[mid+1+j]
    }

    // Merge: Combine sorted arrays
    i, j, k := 0, 0, left

    for i < n1 && j < n2 {
        if leftArr[i] <= rightArr[j] {
            arr[k] = leftArr[i]
            i++
        } else {
            arr[k] = rightArr[j]
            j++
        }
        k++
    }

    // Copy remaining elements
    for i < n1 {
        arr[k] = leftArr[i]
        i++
        k++
    }

    for j < n2 {
        arr[k] = rightArr[j]
        j++
        k++
    }
}
# Template for merge sort using divide and conquer
# Use when: Need stable sort, linked lists, external sorting
# Time: O(n log n), Space: O(n)

def merge_sort(arr, left = 0, right = arr.length - 1)
  return if left >= right

  mid = (left + right) / 2

  # Divide: Sort both halves
  merge_sort(arr, left, mid)
  merge_sort(arr, mid + 1, right)

  # Conquer: Merge sorted halves
  merge(arr, left, mid, right)
end

def merge(arr, left, mid, right)
  left_arr = arr[left..mid]
  right_arr = arr[mid+1..right]

  i = 0
  j = 0
  k = left

  # Merge: Combine sorted arrays
  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

  # Copy remaining elements
  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

Quick Sort

Quick Sort is an in-place sorting algorithm that is often faster than Merge Sort in practice, though its worst-case complexity is $O(N^2)$.

Time:

O(N log N)
(Avg) | Space:
O(log N)

Code Breakdown 

  graph TD
    Input[Array] -->|Partition| P[Partition around Pivot]
    P -->|Divide| Left[Elements < Pivot]
    P -->|Divide| Right[Elements > Pivot]
    Left -->|Recurse Sort| SortedLeft
    Right -->|Recurse Sort| SortedRight

/**
 * Template for quick sort using divide and conquer
 * Use when: Need in-place sorting, average O(n log n)
 * Time: O(n log n) avg, O(n^2) worst, Space: O(log n)
 */
function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        // Partition the array
        const pivotIndex = partition(arr, low, high);

        // Conquer: Recursively sort subarrays
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

function partition(arr, low, high) {
    const pivot = arr[high];  // Choose rightmost element as pivot
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];  // Swap
        }
    }

    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];  // Place pivot
    return i + 1;
}
"""
Template for quick sort using divide and conquer
Use when: Need in-place sorting, average O(n log n)
Time: O(n log n) avg, O(n^2) worst, Space: O(log n)
"""
def quick_sort(arr, low=None, high=None):
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1

    if low < high:
        # Partition the array
        pivot_index = partition(arr, low, high)

        # Conquer: Recursively sort subarrays
        quick_sort(arr, low, pivot_index - 1)
        quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):
    pivot = arr[high]  # Choose rightmost element as pivot
    i = low - 1

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # Swap

    arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot
    return i + 1
/**
 * Template for quick sort using divide and conquer
 * Use when: Need in-place sorting, average O(n log n)
 * Time: O(n log n) avg, O(n^2) worst, Space: O(log n)
 */
public class QuickSort {
    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array
            int pivotIndex = partition(arr, low, high);

            // Conquer: Recursively sort subarrays
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Choose rightmost element as pivot
        int i = low - 1;

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

        // Swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
}
/**
 * Template for quick sort using divide and conquer
 * Use when: Need in-place sorting, average O(n log n)
 * Time: O(n log n) avg, O(n^2) worst, Space: O(log n)
 */
class QuickSort {
public:
    void quickSort(vector<int>& arr, int low, int high) {
        if (low < high) {
            // Partition the array
            int pivotIndex = partition(arr, low, high);

            // Conquer: Recursively sort subarrays
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

private:
    int partition(vector<int>& arr, int low, int high) {
        int pivot = arr[high];  // Choose rightmost element as pivot
        int i = low - 1;

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

        swap(arr[i + 1], arr[high]);  // Place pivot
        return i + 1;
    }
};
/**
 * Template for quick sort using divide and conquer
 * Use when: Need in-place sorting, average O(n log n)
 * Time: O(n log n) avg, O(n^2) worst, Space: O(log n)
 */
func quickSort(arr []int, low int, high int) {
    if low < high {
        // Partition the array
        pivotIndex := partition(arr, low, high)

        // Conquer: Recursively sort subarrays
        quickSort(arr, low, pivotIndex-1)
        quickSort(arr, pivotIndex+1, high)
    }
}

func partition(arr []int, low int, high int) int {
    pivot := arr[high]  // Choose rightmost element as pivot
    i := low - 1

    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}
# Template for quick sort using divide and conquer
# Use when: Need in-place sorting, average O(n log n)
# Time: O(n log n) avg, O(n^2) worst, Space: O(log n)

def quick_sort(arr, low = 0, high = arr.length - 1)
  if low < high
    # Partition the array
    pivot_index = partition(arr, low, high)

    # Conquer: Recursively sort subarrays
    quick_sort(arr, low, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, high)
  end
end

def partition(arr, low, high)
  pivot = arr[high]  # Choose rightmost element as pivot
  i = low - 1

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

  arr[i + 1], arr[high] = arr[high], arr[i + 1]  # Place pivot
  i + 1
end

Binary Search

Binary Search is the simplest form of Divide and Conquer, where we discard half the problem space at each step.

Time:

O(log N)
| Space:
O(1)
(Iterative)

Code Breakdown 

  graph TD
    Start[Search Range] --> Check{Middle == Target?}
    Check -->|Yes| Found[Return Index]
    Check -->|No| Compare{Middle > Target?}
    Compare -->|Yes| Left[Search Left Half]
    Compare -->|No| Right[Search Right Half]
    Left --> Start
    Right --> Start

/**
 * Template for binary search
 * Use when: Searching in sorted arrays
 * Time: O(log n), Space: O(1) iterative
 */
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}
"""
Template for binary search
Use when: Searching in sorted arrays
Time: O(log n), Space: O(1) iterative
"""
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
/**
 * Template for binary search
 * Use when: Searching in sorted arrays
 * Time: O(log n), Space: O(1) iterative
 */
public class BinarySearch {
    public int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

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

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}
/**
 * Template for binary search
 * Use when: Searching in sorted arrays
 * Time: O(log n), Space: O(1) iterative
 */
class BinarySearch {
public:
    int binarySearch(vector<int>& arr, int target) {
        int left = 0;
        int right = arr.size() - 1;

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

            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};
/**
 * Template for binary search
 * Use when: Searching in sorted arrays
 * Time: O(log n), Space: O(1) iterative
 */
func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1

    for left <= right {
        mid := left + (right-left)/2

        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return -1
}
# Template for binary search
# Use when: Searching in sorted arrays
# Time: O(log n), Space: O(1) iterative

def binary_search(arr, target)
  left = 0
  right = arr.length - 1

  while left <= right
    mid = (left + right) / 2

    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end

  -1
end

Practice

Link your understanding to practice with the Problems page.