Merge Sort in C: Algorithm, Code, and Complete Guide

Merge sort in C is a widely used sorting algorithm that follows the divide-and-conquer approach. Instead of sorting an entire array at once, it repeatedly splits the array into smaller halves, sorts those smaller sections recursively, and then merges them back together in the correct order to produce a fully sorted array.

Because of its consistent O(n log n) time complexity and ability to handle large datasets efficiently, merge sort is considered one of the most reliable sorting algorithms in computer science. It is commonly used in applications where stable and predictable sorting performance is required.

In this blog, you will learn exactly how merge sort works, how to write merge sort code in C from scratch, how to trace through a dry run, and where it is actually used in real-world systems. 

Transform your career with upGrad’s Data Science Course. Learn from industry experts, work on hands-on projects, and gain the skills top employer’s demand. 

What Is Merge Sort in C?

The key idea is simple: sorting two small arrays and merging them is far easier than sorting one large array directly.

Here is the high-level flow:

This process repeats until each sub-array has only one element, which is already considered sorted.

Why Use Merge Sort?

Feature	Merge Sort	Bubble Sort	Quick Sort
Time Complexity (Worst)	O(n log n)	O(n²)	O(n²)
Time Complexity (Best)	O(n log n)	O(n)	O(n log n)
Space Complexity	O(n)	O(1)	O(log n)
Stable Sort	Yes	Yes	No
Best for Large Data	Yes	No	Yes

Merge sort algorithm in C is preferred when:

• You need a stable sort (equal elements preserve their original order)
• You are working with linked lists (merge sort is ideal here)
• Your dataset is large and performance matters
• You are sorting external data (files stored on disk)

Also Read: Types of Linked Lists

Merge Sort Algorithm in C: Step-by-Step

Before writing any merge sort program in C, understand the two core functions you need to build:

1. mergeSort(): recursively divides the array
2. merge(): merges two sorted halves back together

The Divide Step

mergeSort(arr, left, right)
   if left < right:
       mid = (left + right) / 2
       mergeSort(arr, left, mid)
       mergeSort(arr, mid + 1, right)
       merge(arr, left, mid, right)

Also Read: Insertion Sort in C: Algorithm, Code, and Step-by-Step Guide 

The Merge Step

The merge step takes two sorted sub-arrays and combines them into one sorted array. It uses a temporary array to hold values while comparing elements from both halves.

Dry Run Example

Let's trace merge sort on the array: [38, 27, 43, 3]

Step 1: Divide

[38, 27, 43, 3]
 [38, 27]   [43, 3]
[38] [27]  [43]  [3]

Step 2: Merge

[38] + [27] → [27, 38]
[43] + [3]  → [3, 43]
[27, 38] + [3, 43] → [3, 27, 38, 43]

Each merge step compares elements from both halves one by one and places the smaller one first. This is what makes the final result sorted.

Also Read: Data Structures and Algorithms (DSA)

Merge Sort Code in C: Full Implementation

Here is the complete merge sort implementation in C:

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

// Merge two sorted sub-arrays into one
void merge(int arr[], int left, int mid, int right) {
   int n1 = mid - left + 1;
   int n2 = right - mid;

   // Create temporary arrays
   int *L = (int *)malloc(n1 * sizeof(int));
   int *R = (int *)malloc(n2 * sizeof(int));

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

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

   // Copy remaining elements of L, if any
   while (i < n1) {
       arr[k] = L[i];
       i++;
       k++;
   }

   // Copy remaining elements of R, if any
   while (j < n2) {
       arr[k] = R[j];
       j++;
       k++;
   }

   free(L);
   free(R);
}

// Recursive function to divide and sort
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);
   }
}

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

// Main function
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:

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

Key Points About This Code

• malloc is used to create temporary arrays inside the merge() function. Always free() them afterward to avoid memory leaks.
• mid = left + (right - left) / 2 is used instead of (left + right) / 2 to prevent integer overflow on large arrays.
• The recursion stops when left >= right, which means the sub-array has one or zero elements.

Also Read: Understanding While Loop in Python with Examples

Time and Space Complexity of Merge Sort in C

Understanding complexity is essential for any developer. Here is what merge sort looks like across different cases:

Time Complexity

Case	Complexity	When It Happens
Best Case	O(n log n)	Always, regardless of input
Average Case	O(n log n)	Randomly ordered input
Worst Case	O(n log n)	Even reverse-sorted arrays

This is one of merge sort's biggest strengths. Unlike quick sort, the worst case for merge sort never degrades to O(n²).

The log n factor comes from the number of times you can divide the array in half. The n factor comes from the work done during each merge step.

Also Read: Time and Space Complexity in Machine Learning Algorithms Explained

Space Complexity

Merge sort requires O(n) auxiliary space because it creates temporary arrays during the merge step. This is its main drawback compared to in-place algorithms like quick sort or heap sort.

For memory-constrained environments, this is worth considering before choosing merge sort.

Recurrence Relation

The recurrence relation for merge sort algorithm in C is:

T(n) = 2T(n/2) + O(n)
Solving this using the Master Theorem gives us O(n log n).

Also Read: Top Time Complexities that every Programmer Should Learn

Merge Sort Program in C: Iterative (Bottom-Up) Approach

The recursive approach is clean and easy to understand. But for very deep recursion (large arrays), stack overflow can be a concern. The iterative (bottom-up) approach solves this.

Instead of dividing top-down, it merges from the bottom up, starting with sub-arrays of size 1, then 2, then 4, and so on.

#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++];
       else arr[k++] = R[j++];
   }
   while (i < n1) arr[k++] = L[i++];
   while (j < n2) arr[k++] = R[j++];

   free(L);
   free(R);
}

void mergeSortIterative(int arr[], int n) {
   for (int size = 1; size < n; size *= 2) {
       for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1 < n - 1) ? left + 2 * size - 1 : n - 1;
            merge(arr, left, mid, right);
       }
   }
}

int main() {
   int arr[] = {12, 11, 13, 5, 6, 7};
   int n = sizeof(arr) / sizeof(arr[0]);

   mergeSortIterative(arr, n);

   printf("Sorted: ");
   for (int i = 0; i < n; i++) printf("%d ", arr[i]);
   printf("\n");

   return 0;
}

Output: Sorted: 5 6 7 11 12 13 

When to use the iterative version:

• When input arrays are very large (thousands to millions of elements)
• When you want to avoid stack overhead from deep recursion
• In embedded or system programming where stack size is limited

Also Read: Top 12 Stack Examples in Real Life

Where Is Merge Sort Used in Real Life?

Merge sort is not just a textbook algorithm. It shows up in real systems regularly.

Practical Applications

• External sorting: When data cannot fit in memory, merge sort is used to sort data stored on disk. It reads chunks, sorts them, and merges sorted files.
• Sorting linked lists: Unlike arrays, linked lists do not support random access. Merge sort works perfectly because it only needs sequential access.
• Inversion count problems: Merge sort can count the number of inversions in an array in O(n log n) time.
• Stable sorting in databases: Merge sort preserves the relative order of equal elements, which is critical for multi-key sorting in SQL and other databases.
• Parallel processing: Merge sort is naturally parallelizable. Each half can be sorted on a separate processor and merged at the end.

Merge Sort vs Quick Sort: When to Choose What

Criterion	Merge Sort	Quick Sort
Worst-case time	O(n log n)	O(n²)
Memory usage	O(n)	O(log n)
Stable sort	Yes	No
Linked lists	Preferred	Not ideal
In-place sorting	No	Yes
Cache efficiency	Lower	Higher

Use merge sort when stability matters or when you are sorting linked lists. Use quick sort when memory is limited and data is in an array.

Common Mistakes in Merge Sort Implementation in C

Even experienced programmers make these mistakes when writing merge sort code in C:

• Not freeing malloc'd memory: Always call free(L) and free(R) after merging. Skipping this causes memory leaks.
• Integer overflow in mid calculation: Use mid = left + (right - left) / 2, not (left + right) / 2.
• Off-by-one errors in boundaries: Be careful with left, mid, and right indices. The left half is [left, mid] and the right half is [mid+1, right].
• Forgetting the base case: The recursion must stop when left >= right. Without this check, the program will crash with a stack overflow.
• Copying indices instead of values: Always copy actual array values into temporary arrays, not index references.

Conclusion

Merge sort in C is a powerful, stable, and consistent sorting algorithm with a guaranteed O(n log n) time complexity in all cases. It is clean to implement, easy to reason about, and widely used in both competitive programming and production systems.

Start with the recursive version to understand the logic. Then try the iterative version to see how it avoids recursion overhead. Once you are comfortable, explore merge sort's role in counting inversions and external sorting to see just how versatile this algorithm really is.

Want personalized guidance on AI and upskilling? Speak with an expert for a free 1:1 counselling session today.