Divide and Conquer Strategy and Recurrence Relations in DSA C

Mental Model

Break a big problem into smaller similar problems, solve each one, then combine results.

Analogy: Like cutting a big cake into smaller pieces, eating each piece, then feeling full from the whole cake.

Big Problem
   ↓
+----------+
| Divide   |
+----------+
   ↓ ↓ ↓
Small Problems
   ↓ ↓ ↓
+----------+
| Conquer  |
+----------+
   ↓
Combine Results
   ↓
Solution

Dry Run Walkthrough

Input: Sort array: [4, 2, 7, 1]

Goal: Sort the array using divide and conquer by splitting, sorting, and merging

Step 1: Divide array into two halves: [4, 2] and [7, 1]

[4, 2, 7, 1]
Split -> [4, 2] and [7, 1]

Why: We break the big problem into smaller parts to handle easily

Step 2: Divide [4, 2] into [4] and [2]

[4] and [2]
Each is a single element

Why: Single elements are already sorted, base case reached

Step 3: Merge [4] and [2] into sorted [2, 4]

[2, 4]

Why: Combine sorted parts to get bigger sorted array

Step 4: Divide [7, 1] into [7] and [1]

[7] and [1]

Why: Again, base case with single elements

Step 5: Merge [7] and [1] into sorted [1, 7]

[1, 7]

Why: Combine sorted parts

Step 6: Merge sorted halves [2, 4] and [1, 7] into [1, 2, 4, 7]

[1, 2, 4, 7]

Why: Final combine step to get fully sorted array

Result:

[1, 2, 4, 7] -- sorted array

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

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

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // find middle
        mergeSort(arr, left, mid); // sort left half
        mergeSort(arr, mid + 1, right); // sort right half
        merge(arr, left, mid, right); // merge sorted halves
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 7, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

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

divide problem into two halves

mergeSort(arr, left, mid); // sort left half

recursively conquer left half

mergeSort(arr, mid + 1, right); // sort right half

recursively conquer right half

merge(arr, left, mid, right); // merge sorted halves

combine sorted halves into one sorted array

while (i < n1 && j < n2) { ... }

merge elements from two halves in order

Output

Original array: 4, 2, 7, 1

Sorted array: 1, 2, 4, 7

Complexity Analysis

Time: O(n log n) because the array is divided into halves log n times and merging takes O(n) each time

Space: O(n) because temporary arrays are used during merging

vs Alternative: Naive sorting like bubble sort is O(n^2), much slower for large n; divide and conquer is more efficient

Edge Cases

Empty array

No sorting needed, function returns immediately

DSA C

if (left < right) {

Single element array

Already sorted, recursion stops immediately

DSA C

if (left < right) {

Array with duplicate elements

Duplicates are handled correctly and appear in sorted order

DSA C

if (L[i] <= R[j]) {

When to Use This Pattern

When a problem can be split into smaller similar problems and combined, use divide and conquer to solve efficiently.

Common Mistakes

Mistake: Not handling base case properly causing infinite recursion
Fix: Add condition to stop recursion when subarray size is 1 or 0 (if left < right)

Mistake: Incorrect merging causing unsorted output
Fix: Carefully compare elements from both halves and copy in sorted order

Summary

It breaks a problem into smaller parts, solves each, then combines results.

Use it when a problem can be divided into similar subproblems.

The key is to divide, conquer recursively, and then merge results.