Merge Sort as Divide and Conquer in DSA C

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a big pile of cards by splitting them into smaller piles, sorting each small pile, then carefully merging the piles back together in order.

Original array:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split again:
[38] [27, 43]   [3, 9] [82, 10]

Split until single elements:
[38] [27] [43]   [3] [9] [82] [10]

Dry Run Walkthrough

Input: array: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the array in ascending order using merge sort

Step 1: Split array into two halves: left=[38,27,43], right=[3,9,82,10]

[38, 27, 43]   [3, 9, 82, 10]

Why: Divide the problem into smaller parts to sort separately

Step 2: Split left half into [38] and [27, 43]

[38]   [27, 43]   [3, 9, 82, 10]

Why: Keep dividing until subarrays have one element

Step 3: Split [27, 43] into [27] and [43]

[38]   [27]   [43]   [3, 9, 82, 10]

Why: Single elements are sorted by definition

Step 4: Merge [27] and [43] into sorted [27, 43]

[38]   [27, 43]   [3, 9, 82, 10]

Why: Combine sorted parts to build bigger sorted arrays

Step 5: Merge [38] and [27, 43] into sorted [27, 38, 43]

[27, 38, 43]   [3, 9, 82, 10]

Why: Merge sorted left half completely

Step 6: Split right half into [3, 9] and [82, 10]

[27, 38, 43]   [3, 9]   [82, 10]

Why: Divide right half to smaller parts

Step 7: Split [3, 9] into [3] and [9]

[27, 38, 43]   [3]   [9]   [82, 10]

Why: Single elements are sorted

Step 8: Merge [3] and [9] into [3, 9]

[27, 38, 43]   [3, 9]   [82, 10]

Why: Merge sorted small parts

Step 9: Split [82, 10] into [82] and [10]

[27, 38, 43]   [3, 9]   [82]   [10]

Why: Divide until single elements

Step 10: Merge [82] and [10] into [10, 82]

[27, 38, 43]   [3, 9]   [10, 82]

Why: Merge sorted small parts

Step 11: Merge [3, 9] and [10, 82] into [3, 9, 10, 82]

[27, 38, 43]   [3, 9, 10, 82]

Why: Merge sorted right half completely

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into fully sorted [3, 9, 10, 27, 38, 43, 82]

[3, 9, 10, 27, 38, 43, 82]

Why: Final merge to get fully sorted array

Result:

[3, 9, 10, 27, 38, 43, 82]

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;
        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[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, size - 1);

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

    return 0;
}

if (left < right) {

check if subarray has more than one element to continue dividing

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

find middle index to split array

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

recursively sort left half

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

recursively sort right half

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

combine two sorted halves into one sorted array

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

merge elements by comparing left and right subarrays

while (i < n1) {

copy remaining elements from left subarray if any

while (j < n2) {

copy remaining elements from right subarray if any

Output

Original array:

38, 27, 43, 3, 9, 82, 10

Sorted array:

3, 9, 10, 27, 38, 43, 82

Complexity Analysis

Time: O(n log n) because the array is repeatedly split in half (log n splits) and merging takes O(n) at each level

Space: O(n) because temporary arrays are used to merge subarrays

vs Alternative: Compared to simple sorting like bubble sort O(n^2), merge sort is much faster for large arrays due to divide and conquer

Edge Cases

empty array

function returns immediately without changes

DSA C

if (left < right) {

array with one element

function returns immediately as single element is already sorted

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 you see a problem asking to sort or organize data efficiently by breaking it into smaller parts, reach for merge sort because it uses divide and conquer to sort in O(n log n) time.

Common Mistakes

Mistake: Not checking the base case properly causing infinite recursion
Fix: Add condition if (left < right) to stop recursion when subarray has one or zero elements

Mistake: Merging without copying remaining elements from left or right subarray
Fix: Add loops to copy leftover elements after main merge loop

Mistake: Calculating mid as (left + right) / 2 without handling large indices
Fix: Calculate mid as left + (right - left) / 2 to avoid overflow

Summary

Merge sort splits the array into smaller parts, sorts them, and merges back to get a sorted array.

Use merge sort when you want a reliable, efficient sorting method especially for large data.

The key insight is dividing the problem into smaller sorted pieces and merging them carefully.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Divide the array into halves, sort each half, then merge them

B. Sort the array by repeatedly swapping adjacent elements

C. Select a pivot and partition the array around it

D. Insert elements one by one into a sorted sublist

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   After splitting, it merges the sorted halves back to form a sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option A

4. Quick Check:

   Merge Sort = Divide and Conquer [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses a pivot like Quick Sort
• Believing Merge Sort sorts in place without merging

2. Which of the following is the correct base case condition in a recursive Merge Sort function in C?

easy

A. if (start >= end) return;

B. if (start > end) return;

C. if (start == end) return;

D. if (start != end) return;

Solution

1. Step 1: Identify when recursion should stop

   Merge Sort stops splitting when the subarray has one or zero elements, i.e., start >= end.

2. Step 2: Choose the correct condition

   The base case is when start >= end, so return without further splitting.

3. Final Answer:

   if (start >= end) return; -> Option A

4. Quick Check:

   Base case = start >= end [OK]

Hint: Stop recursion when start >= end [OK]

Common Mistakes:

• Using == instead of >= risks issues if start > end
• Using > misses the single element case
• Using != returns too early, breaking recursion

3. What will be the output of the following C code snippet after calling mergeSort(arr, 0, 4); on int arr[] = {5, 3, 8, 4, 2};?

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    mergeSort(arr, 0, 4);
    for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
    return 0;
}

medium

A. 5 3 8 4 2

B. 8 5 4 3 2

C. 2 3 4 5 8

D. 2 4 3 5 8

Solution

1. Step 1: Understand mergeSort splits and merges

   The array is recursively split into halves and merged in sorted order.

2. Step 2: Trace the final sorted array

   After full recursion and merging, the array becomes sorted: 2 3 4 5 8.

3. Final Answer:

   2 3 4 5 8 -> Option C

4. Quick Check:

   Sorted array output = 2 3 4 5 8 [OK]

Hint: Merge Sort always outputs sorted array [OK]

Common Mistakes:

• Thinking mergeSort does not change original array
• Confusing mergeSort with reverse sorting
• Ignoring the merge step results in unsorted output

4. Identify the error in the following merge function snippet used in Merge Sort:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i <= n1; i++) L[i] = arr[l + i];
    for (int j = 0; j <= n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

medium

A. The merge function should not use temporary arrays

B. The loops copying to L and R arrays use <= instead of < causing out-of-bounds access

C. The size of arrays L and R is calculated incorrectly

D. The merge condition should be L[i] < R[j] instead of <= to avoid duplicates

Solution

1. Step 1: Check array copying loops

   The loops use i <= n1 and j <= n2 which causes index to go out of bounds since arrays are 0-based.

2. Step 2: Correct loop condition

   Loops should use i < n1 and j < n2 to avoid accessing invalid memory.

3. Final Answer:

   The loops copying to L and R arrays use <= instead of < causing out-of-bounds access -> Option B

4. Quick Check:

   Loop bounds must be less than array size [OK]

Hint: Use < not <= in loops for array indexing [OK]

Common Mistakes:

• Using <= causes buffer overflow errors
• Confusing array size with last index
• Ignoring array indexing starting at 0

5. You want to sort a linked list using Merge Sort. Which of the following is the best approach to split the list into two halves efficiently?

hard

A. Convert the list to an array, sort it, then rebuild the list

B. Count the total nodes first, then traverse again to the middle node

C. Split the list by breaking after the first node repeatedly

D. Use two pointers: move one pointer twice as fast as the other to find the middle

Solution

1. Step 1: Understand splitting linked list for Merge Sort

   Using two pointers (slow and fast), where fast moves twice as fast, helps find the middle in one pass.

2. Step 2: Compare other methods

   Counting nodes requires two passes; breaking after first node is incorrect; converting to array is inefficient.

3. Final Answer:

   Use two pointers: move one pointer twice as fast as the other to find the middle -> Option D

4. Quick Check:

   Two-pointer technique = efficient split [OK]

Hint: Use slow-fast pointer to find middle in one pass [OK]

Common Mistakes:

• Counting nodes wastes time with two traversals
• Breaking after first node does not split evenly
• Converting to array loses linked list benefits