Merge Sort Algorithm: Complete Guide with C Implementation

The merge sort algorithm is one of the most important and efficient sorting algorithms in computer science. Whether you are preparing for coding interviews, learning data structures, or implementing high-performance applications, understanding the merge sort algorithm is essential.

In this complete guide, you will learn:

What the merge sort algorithm is
How merge sort works step by step
Time and space complexity analysis
Advantages and disadvantages of merge sort
A full C implementation of merge sort with explanation

What Is the Merge Sort Algorithm?

The merge sort algorithm is a divide and conquer sorting algorithm that works by:

Dividing the input array into smaller subarrays
Recursively sorting each subarray
Merging the sorted subarrays to produce the final sorted array

Merge sort was invented by John von Neumann in 1945 and is widely used due to its guaranteed O(n log n) time complexity.

Key Characteristics of Merge Sort Algorithm

The merge sort algorithm has the following important properties:

Time Complexity:
- Best case: O(n log n)
- Average case: O(n log n)
- Worst case: O(n log n)
Space Complexity: O(n) (uses extra memory)
Stable Sorting Algorithm: Maintains the order of equal elements
Not In-Place: Requires auxiliary arrays during merging

How Merge Sort Algorithm Works (Step-by-Step)

The merge sort algorithm follows three main steps:

1. Divide

The array is recursively divided into two halves until each subarray contains only one element.

2. Conquer

Each subarray is sorted recursively.

3. Merge

The sorted subarrays are merged back together in sorted order.

Example of Merge Sort Algorithm

Consider the array:

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

Divide Phase

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

Merge Phase

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

Merge Sort Algorithm in C (Implementation)

Below is a complete and optimized C program for merge sort algorithm.

Merge Function in Merge Sort

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

    int L[n1], R[n2];

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

    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++;
    }
}

The merge function takes two already sorted parts of an array and combines them into one single sorted array.

👉 Important:

Left part is sorted
Right part is sorted
merge() just joins them in correct order

merge Function Signature (What the parameters mean)

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

arr[] → original array
left → starting index of the left subarray
mid → ending index of the left subarray
right → ending index of the right subarray

So the array looks like this:

Left part:  arr[left ... mid]
Right part: arr[mid+1 ... right]

Step-by-Step Explanation

Declare variables

int i, j, k;

i → index for left temporary array
j → index for right temporary array
k → index for original array

Find sizes of left and right subarrays

int n1 = mid - left + 1;
int n2 = right - mid;

This tells us:

n1 → number of elements in left part
n2 → number of elements in right part

Create temporary arrays

int L[n1], R[n2];

Why?
👉 Because we don’t want to overwrite original data while merging.

Copy data into temporary arrays

for (i = 0; i < n1; i++)
    L[i] = arr[left + i];

for (j = 0; j < n2; j++)
    R[j] = arr[mid + 1 + j];

Example:

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

L[] = [3, 27, 38]
R[] = [9, 10, 82]

Reset indexes

i = 0;
j = 0;
k = left;

Start comparing from beginning of L[] and R[]
Start placing result from position left in original array

Compare and merge (MOST IMPORTANT PART)

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

What happens here?

Compare smallest elements of both arrays
Put the smaller one into arr[k]
Move index forward

Example:

Compare 3 and 9 → put 3
Compare 27 and 9 → put 9
Compare 27 and 10 → put 10

Copy remaining elements (if any)

Left array leftovers:

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

Right array leftovers:

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

Why needed?
👉 Sometimes one array finishes early, but the other still has elements.

Final Result After Merge

Left:  [3, 27, 38]
Right: [9, 10, 82]

Merged array:
[3, 9, 10, 27, 38, 82]

One-Line Summary

The merge() function combines two sorted subarrays into a single sorted array by using temporary arrays and comparing elements one by one.

Merge Sort Recursive Function

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);
    }
}

The mergeSort function is responsible for dividing the array into smaller parts, sorting each part, and then merging them back together using the merge() function.

👉 Think of mergeSort() as the brain of the merge sort algorithm.

mergeSort Function Definition

void mergeSort(int arr[], int left, int right)

Parameters explained:

arr[] → the array to be sorted
left → starting index of the array/subarray
right → ending index of the array/subarray

Step-by-Step Explanation

Base Condition (Stopping Condition)

if (left < right)

This line checks:

If the array has more than one element, continue sorting
If left == right, it means only one element → already sorted

📌 This condition prevents infinite recursion.

Find the Middle Index

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

This splits the array into two halves:

Left half → left to mid
Right half → mid + 1 to right

👉 This formula is safer than (left + right) / 2 because it avoids integer overflow.

Recursively Sort the Left Half

mergeSort(arr, left, mid);

What happens here?

The left part is again divided
This continues until each subarray has only one element

Recursively Sort the Right Half

mergeSort(arr, mid + 1, right);

Same process:

Right half is divided further
Sorting continues until smallest possible subarrays are reached

Merge the Sorted Halves

merge(arr, left, mid, right);

At this point:

Left half is already sorted
Right half is already sorted

👉 merge() combines both halves into one sorted subarray

How Recursion Works (Simple Example)

Array:

[38, 27, 43, 3]

Divide Phase:

mergeSort(0,3)
→ mergeSort(0,1)   mergeSort(2,3)
→ mergeSort(0,0) mergeSort(1,1) mergeSort(2,2) mergeSort(3,3)

Each single element is already sorted.

Merge Phase:

merge(0,0,1) → [27, 38]
merge(2,2,3) → [3, 43]
merge(0,1,3) → [3, 27, 38, 43]

Visual Understanding

Divide → Divide → Divide
Single elements

Merge ← Merge ← Merge
Sorted array

One-Line Summary

The mergeSort() function recursively divides the array into smaller subarrays until one element remains, then merges them back in sorted order using the merge() function.

Why `mergeSort()` Is Powerful

Guarantees O(n log n) time complexity
Works efficiently for large datasets
Ensures stable sorting
Perfect example of divide and conquer

Complete Merge Sort Program in C

#include <stdio.h>

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

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

Output of Merge Sort Algorithm

Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82

Time and Space Complexity of Merge Sort Algorithm

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Space Complexity: O(n)
Extra memory is required for merging subarrays.

Advantages of Merge Sort Algorithm

Guaranteed O(n log n) time complexity
Stable sorting algorithm
Excellent for sorting linked lists
Ideal for external sorting (large datasets)
Predictable performance

Disadvantages of Merge Sort Algorithm

Requires extra memory (not in-place)
Slower than quicksort for small arrays
Not adaptive to already sorted data

When Should You Use Merge Sort?

Use the merge sort algorithm when:

You need stable sorting
Worst-case performance must be guaranteed
Working with linked lists
Sorting very large datasets
Implementing parallel or distributed sorting

Conclusion

The merge sort algorithm is a foundational sorting technique that demonstrates the power of divide and conquer. Although it requires extra memory, its stability and guaranteed performance make it one of the most reliable sorting algorithms in computer science.

Mastering merge sort will strengthen your understanding of algorithms and significantly improve your performance in coding interviews and real-world applications.

👉 Next challenge: Try implementing merge sort iteratively or apply it to linked lists.

Happy coding! 🚀

What Is the Merge Sort Algorithm?

Key Characteristics of Merge Sort Algorithm

How Merge Sort Algorithm Works (Step-by-Step)

1. Divide

2. Conquer

3. Merge

Example of Merge Sort Algorithm

Divide Phase

Merge Phase

Merge Sort Algorithm in C (Implementation)

Merge Function in Merge Sort

merge Function Signature (What the parameters mean)

Step-by-Step Explanation

Declare variables

Find sizes of left and right subarrays

Create temporary arrays

Copy data into temporary arrays

Reset indexes

Compare and merge (MOST IMPORTANT PART)

Copy remaining elements (if any)

Final Result After Merge

One-Line Summary

Merge Sort Recursive Function

mergeSort Function Definition

Parameters explained:

Step-by-Step Explanation

Base Condition (Stopping Condition)

Find the Middle Index

Recursively Sort the Left Half

Recursively Sort the Right Half

Merge the Sorted Halves

How Recursion Works (Simple Example)

Divide Phase:

Merge Phase:

Visual Understanding

One-Line Summary

Why mergeSort() Is Powerful

Complete Merge Sort Program in C

Output of Merge Sort Algorithm

Time and Space Complexity of Merge Sort Algorithm

Advantages of Merge Sort Algorithm

Disadvantages of Merge Sort Algorithm

When Should You Use Merge Sort?

Conclusion

See Also

Leave a Comment Cancel reply

Why `mergeSort()` Is Powerful