Merge Sort Algorithm 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 small piles, sorting each small pile, then carefully merging the piles back together in order.

Unsorted list:
[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: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split the list into two halves

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

Why: Splitting helps to break down the problem into smaller parts

Step 2: Split left half again

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

Why: Keep splitting until each part has one element

Step 3: Split right half into two halves

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

Why: Divide the right half to smaller parts for sorting

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

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

Why: Single elements are easier to sort and merge

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

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

Why: Continue splitting until all parts are single elements

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

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

Why: All parts are now single elements

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

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

Why: Merge small sorted parts to build bigger sorted parts

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

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

Why: Merge small sorted parts to build bigger sorted parts

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

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

Why: Merge small sorted parts to build bigger sorted parts

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

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

Why: Merge sorted parts to build bigger sorted parts

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

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

Why: Merge sorted parts to build bigger sorted parts

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 produces the fully sorted list

Result:

Final sorted list:
[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]);

    mergeSort(arr, 0, size - 1);

    printArray(arr, size);
    return 0;
}

if (left < right) {

check if the current part has more than one element to split

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

find middle index to split the array

mergeSort(arr, left, mid);

recursively sort the left half

mergeSort(arr, mid + 1, right);

recursively sort the right half

merge(arr, left, mid, right);

merge the two sorted halves into one sorted part

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

compare elements from left and right parts to merge in order

arr[k] = L[i]; i++;

take element from left part if smaller or equal

arr[k] = R[j]; j++;

take element from right part if smaller

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

copy remaining elements from left part if any

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

copy remaining elements from right part if any

Output

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

Complexity Analysis

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

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

vs Alternative: Compared to simple sorting like bubble sort with O(n^2), merge sort is much faster for large lists 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 kept and sorted correctly

DSA C

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

When to Use This Pattern

When you need to sort a list efficiently and can use extra space, reach for merge sort because it reliably sorts in O(n log n) time by splitting and merging.

Common Mistakes

Mistake: Not handling the base case properly causing infinite recursion
Fix: Add condition to stop recursion when left >= right

Mistake: Incorrectly merging arrays causing unsorted output
Fix: Carefully compare elements from both halves and copy remaining elements after main loop

Mistake: Forgetting to free temporary arrays causing memory leaks
Fix: Call free() on temporary arrays after merging

Summary

Merge sort splits the list into halves, sorts each half, then merges them back in order.

Use merge sort when you want a stable, efficient sorting algorithm with guaranteed O(n log n) time.

The key insight is breaking the problem into smaller sorted parts and merging them carefully.

Practice

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

easy

A. Insert elements one by one into a sorted sublist

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

C. Select a pivot and partition the array around it

D. Sort the array by repeatedly swapping adjacent elements

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

   It then merges these sorted halves to produce a fully sorted array.

3. Final Answer:

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

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 extra space

2. Which of the following is the correct way to declare the merge function header in C for Merge Sort?

easy

A. void merge(int arr[], int left, int mid, int right);

B. int merge(int arr, int left, int mid, int right);

C. void merge(int arr, int left, int mid, int right);

D. int merge(int arr[], int left, int right);

Solution

1. Step 1: Check parameter types for merge function

   The array should be passed as int arr[] and indices as integers.

2. Step 2: Confirm return type

   Merge function usually returns nothing (void) as it modifies the array in place.

3. Final Answer:

   void merge(int arr[], int left, int mid, int right); -> Option A

4. Quick Check:

   Correct signature = void merge(int arr[], int left, int mid, int right); [OK]

Hint: Array as int arr[], return void for merge [OK]

Common Mistakes:

• Passing array as int arr instead of int arr[]
• Using int return type instead of void
• Missing the mid parameter needed for merging

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

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    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++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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

medium

A. [3, 5, 4, 2, 8]

B. [5, 3, 8, 4, 2]

C. [2, 3, 4, 5, 8]

D. [8, 5, 4, 3, 2]

Solution

1. Step 1: Understand recursive splitting

   The array is split into halves recursively until single elements remain: [5,3,8,4,2] -> [5,3,8] and [4,2], then further splits.

2. Step 2: Merge sorted halves step-by-step

   After sorting and merging, the final array becomes sorted in ascending order: [2, 3, 4, 5, 8].

3. Final Answer:

   [2, 3, 4, 5, 8] -> Option C

4. Quick Check:

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

Hint: Merge Sort always returns sorted array ascending [OK]

Common Mistakes:

• Assuming original array remains unchanged
• Confusing mergeSort with other sorting algorithms
• Forgetting to merge after recursive calls

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

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    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++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

medium

A. The array sizes n1 and n2 are calculated incorrectly

B. The merge function should return an int instead of void

C. The while loops conditions should be i <= n1 and j <= n2

D. The for loops use <= instead of < causing out-of-bounds access

Solution

1. Step 1: Check for loop boundary errors

   The for loops use <= which causes the loop to run one extra time, leading to out-of-bounds array access.

2. Step 2: Correct loop conditions

   Changing <= to < fixes the loops to iterate exactly n1 and n2 times without overflow.

3. Final Answer:

   The for loops use <= instead of < causing out-of-bounds access -> Option D

4. Quick Check:

   Loop boundary off by one = The for loops use <= instead of < causing out-of-bounds access [OK]

Hint: Use <, not <=, for array index loops [OK]

Common Mistakes:

• Using <= in loops causing overflow
• Confusing return type of merge function
• Changing while loop conditions incorrectly

5. Given an array int arr[] = {12, 11, 13, 5, 6, 7};, how many total merge operations will be performed during a full Merge Sort on this array?

hard

A. 5

B. 7

C. 6

D. 8

Solution

1. Step 1: Understand merge operations count

   For an array of size n, Merge Sort performs n-1 merge operations combining subarrays stepwise.

2. Step 2: Calculate for n=6

   Here, n=6, so total merges = 6 - 1 = 5 merges.

3. Step 3: Count merges carefully

   Levels: - Level 1: 3 merges (pairs of size 1) - Level 2: 2 merges (subarrays of size 2 and 3) Total merges = 3 + 2 = 5 merges.

4. Final Answer:

   5 -> Option A

5. Quick Check:

   Count merges per level = 5 [OK]

Hint: Count merges per level, sum all levels [OK]

Common Mistakes:

• Assuming merges = n-1 without counting levels
• Counting only one level of merges
• Confusing merge operations with comparisons