Sorting is an important part of programming because it helps arrange data in a specific order. For example, you may need to arrange numbers from smallest to largest or sort student marks before displaying the results. C programming provides different sorting methods to handle these tasks, and merge sort is one of the commonly used algorithms.
If you are learning data structures and algorithms, understanding merge sort code in C can help you improve your problem-solving skills. Merge sort works by dividing an array into smaller parts, sorting those parts, and combining them to produce a sorted array. This approach makes it useful when working with large amounts of data.
In this blog, you will learn how the merge sort algorithm works, how to write a C program to implement it, and how to understand its output. We will also explore its time complexity, space complexity, advantages, and limitations using simple examples.
What Is Merge Sort in C?
Merge sort is a sorting algorithm used to arrange elements in an array in ascending or descending order. It follows a simple idea: divide the data into smaller parts, sort each part, and merge them back together in the correct order.
In C programming, merge sort is usually implemented using arrays, functions, and recursion. The algorithm continues dividing the array until each part contains only one element. Since a single element is already sorted, the algorithm then combines these smaller parts to create a fully sorted array.
For example, consider the following array:
int arr[] = {8, 3, 6, 2, 7, 1};After applying merge sort, the array becomes:
1 2 3 6 7 8Unlike some basic sorting methods that repeatedly compare and swap elements, merge sort divides the problem into smaller tasks and combines their results. This approach makes it useful for sorting large datasets efficiently.
How the Merge Sort Algorithm Works?
The merge sort algorithm follows three main steps:
- 1. Divide: Split the array into two smaller parts.
- 2. Sort: Continue dividing each part until only one element remains in each part.
- 3. Merge: Compare the elements in the smaller parts and combine them in sorted order.
For example, the array {8, 3, 6, 2} is first divided into {8, 3} and {6, 2}. These parts are divided again into individual elements. Finally, the elements are merged in the correct order to produce {2, 3, 6, 8}.
This process is repeated until the entire array is sorted. Merge sort commonly uses recursion to handle the repeated division and a separate merge function to combine the sorted parts.
Why Merge Sort Is Used to Sort an Array?
Merge sort is useful because it can sort large arrays without relying on repeated comparisons across the entire unsorted array. Its time complexity is \(O(n \log n)\) in the best, average, and worst cases for a standard implementation.
Another advantage is that merge sort is a stable sorting algorithm when implemented correctly. This means that elements with equal values maintain their original relative order.
However, merge sort usually requires additional memory to merge the elements. For this reason, choosing it over another sorting algorithm depends on the size of the data, available memory, and the requirements of the program.
In the next section, we will look at how the merge sort algorithm divides an array, sorts its smaller parts, and merges them step by step.
How the Merge Sort Algorithm Works Step by Step?
To understand merge sort in C, it is helpful to follow how the algorithm handles an array from beginning to end. Instead of sorting all the elements at once, it breaks the array into smaller parts and combines them in sorted order.
Consider this array as an example:
int arr[] = {8, 3, 6, 2};The goal is to arrange these elements in ascending order, producing {2, 3, 6, 8}. Let us see how each step works.
Divide the Array into Smaller Parts
The first step is to divide the array into two parts. For the example above, the array {8, 3, 6, 2} can be split into {8, 3} and {6, 2}.
Each part is then divided again until every part contains only one element. The process looks like this:
{8, 3, 6, 2}
/ \
{8, 3} {6, 2}
/ \ / \
{8} {3} {6} {2}At this stage, no further division is needed because an array containing a single element is already sorted. The algorithm can now start combining the elements.
Sort Each Part Using Recursion
Merge sort uses recursion to repeat the same process on smaller parts of the array. A recursive function calls itself with a smaller section of the input until it reaches a stopping condition.
In merge sort, the stopping condition is reached when a section contains only one element. The function then returns, allowing the previous calls to continue.
For example, {8, 3} is divided into {8} and {3}. Since both parts contain one element, the algorithm can combine them into {3, 8}. In the same way, {6, 2} becomes {2, 6}.
This repeated division and return process is what allows the merge sort algorithm to handle arrays of different sizes.
Merge Two Sorted Arrays into One
Once the smaller parts are sorted, merge sort combines them by comparing their elements and selecting the smaller value first.
Using our example, the two sorted parts are {3, 8} and {2, 6}. The algorithm compares the first elements of both parts and places the smaller one into the final array.
The process continues until all elements have been copied into the correct order:
Sorted part 1: {3, 8}
Sorted part 2: {2, 6}
Final sorted array: {2, 3, 6, 8}The merge operation preserves the order of the elements while combining the two parts. This step is repeated until the complete array is sorted.
Now that you understand how merge sort divides, processes, and combines an array, the next section will show the complete merge sort code in C with an example.
Merge Sort Code in C with Example
Now that we understand how the merge sort algorithm works, let us implement it in C. The program uses two functions: one to divide the array recursively and another to merge the smaller parts in sorted order.
C Program to Implement Merge Sort
The following C program sorts an array of integers in ascending order using merge sort.
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
int temp[right - left + 1];
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left, k = 0; i <= right; i++, k++) {
arr[i] = temp[k];
}
}
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);
}
}
int main() {
int arr[] = {8, 3, 6, 2, 7, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
mergeSort(arr, 0, n - 1);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}Input and Output of the Merge Sort Program
In this example, the array is defined directly inside the C program. The program sorts six integers in ascending order.
Input array:
8 3 6 2 7 1Output:
Original array: 8 3 6 2 7 1
Sorted array: 1 2 3 6 7 8The program first displays the original array. It then calls the mergeSort() function to sort the elements and prints the result.
Explanation of the Merge Sort C Program
The program uses three main parts to complete the sorting process.
- 1.
main()function: Creates the array, calculates its size, displays the original elements, and calls the sorting function. - 2.
mergeSort()function: Divides the array into smaller parts using recursion. It continues until each part contains only one element. - 3.
merge()function: Compares elements from the two sorted parts and stores them in temporary storage in the correct order. It then copies the merged elements back into the original array.
The condition if (left < right) prevents unnecessary division when a section contains only one element. The middle index separates the array into two parts, and the recursive calls sort each part before the merge function combines them.
One important detail is the use of arr[i] <= arr[j] when comparing elements. This ensures that equal elements from the left part are placed first, helping the algorithm maintain stability.
Together, these functions demonstrate how to implement merge sort in C using recursion and a separate merge operation. Next, let us look more closely at how two sorted arrays are merged into one.
How to Merge Two Sorted Arrays in C?
Key point: Merging is the most important part of the merge sort algorithm. It compares elements from two sorted parts of an array and combines them into one sorted sequence.
For example, consider these two sorted arrays:
int arr1[] = {3, 8};
int arr2[] = {2, 6};The goal is to merge them into a single sorted array: {2, 3, 6, 8}. To achieve this, the algorithm compares the elements in both arrays and selects the smaller element first.
Comparing Elements from Both Arrays
The merge operation starts by comparing the first element of each sorted part. If the first element of the left part is smaller, it is copied into the temporary array. Otherwise, the first element of the right part is copied.
For our example, the comparison begins with 3 and 2. Since 2 is smaller, it is copied first. The algorithm then compares 3 and 6, so 3 is copied next. Finally, it compares 8 and 6, placing 6 before 8.
This comparison continues until one of the sorted parts has no remaining elements.
Combining Elements in Sorted Order
After the comparisons, any remaining elements from either part are copied into the temporary array. This is necessary because one part may still contain elements after the other part has been fully processed.
The merging process can be shown as follows:
| Step | Action | Merged elements |
|---|---|---|
| 1 | Compare 3 and 2; select 2 | 2 |
| 2 | Compare 3 and 6; select 3 | 2, 3 |
| 3 | Compare 8 and 6; select 6 | 2, 3, 6 |
| 4 | Copy the remaining 8 | 2, 3, 6, 8 |
Once all elements are merged, the temporary array contains the elements in sorted order. In the C program, these elements are then copied back into the original array.
This process allows merge sort to combine smaller sorted parts into larger sorted parts until the entire array is arranged correctly. Next, we will look at the time and space complexity of merge sort to understand how efficiently it handles different input sizes.
Merge Sort Time Complexity and Space Complexity
Merge sort is known for sorting large arrays efficiently because it divides the input into smaller parts and combines them in sorted order. To understand how well this sorting algorithm performs, we need to look at its time complexity and space complexity.
Time complexity describes how the running time grows as the number of elements increases. Space complexity describes how much additional memory the algorithm needs while sorting the array.
Best-Case Time Complexity of Merge Sort
The best-case time complexity of merge sort is \(O(n \log n)\), where \(n\) represents the number of elements in the array.
Even if the input array is already sorted, the standard merge sort algorithm still divides the array into smaller parts and merges them again. Therefore, it performs a similar amount of work regardless of the initial order of the elements.
For example, an already sorted array such as {1, 2, 3, 4, 5, 6} still goes through the division and merging process. This makes merge sort a reliable choice when predictable sorting performance is important.
Average-Case and Worst-Case Time Complexity
The average-case and worst-case time complexity of merge sort are also \(O(n \log n)\).
This happens because the algorithm divides the array into roughly equal parts at each level. The number of division levels grows logarithmically with the input size, while merging all elements at each level takes linear time.
The following table summarises the time complexity:
| Case | Time complexity |
|---|---|
| Best case | \(O(n \log n)\) |
| Average case | \(O(n \log n)\) |
| Worst case | \(O(n \log n)\) |
This consistent performance is one of the main advantages of merge sort. Unlike some other sorting algorithms, its worst-case running time does not become quadratic for an ordinary array-based implementation.
Space Complexity of the Merge Sort Algorithm
The typical array-based merge sort implementation uses \(O(n)\) auxiliary space because it needs temporary storage to merge elements into sorted order.
In the C program above, the merge() function creates a temporary array to hold the merged elements before copying them back into the original array. The recursive calls also use some additional memory on the call stack, which grows proportionally to \(O(\log n)\).
Therefore, the overall auxiliary space complexity remains \(O(n)\), as the temporary storage takes more space than the recursion stack for large arrays.
Although merge sort requires extra memory, it offers predictable performance and works well when sorting large datasets. Understanding these trade-offs helps you decide when to use merge sort instead of another sorting algorithm.
Advantages and Disadvantages of Merge Sort
Advantages of Using Merge Sort
- 1. Efficient sorting: Merge sort has a time complexity of \(O(n \log n)\) in the best, average, and worst cases.
- 2. Suitable for large arrays: It can sort large amounts of data without the poor worst-case performance seen in some simpler sorting algorithms.
- 3. Stable sorting: When implemented correctly, it preserves the original order of elements with equal values.
- 4. Uses recursion effectively: The algorithm divides a large problem into smaller parts, making the sorting process easier to understand and implement.
- 5. Predictable performance: Its running time remains \(O(n \log n)\) regardless of whether the input array is already sorted, randomly arranged, or in reverse order.
Limitations of Merge Sort Compared with Other Sorting Algorithms
- 1. Requires extra memory: A typical array-based implementation needs \(O(n)\) additional space for merging.
- 2. More code to write: Implementing merge sort in C requires separate functions for dividing the array and merging the sorted parts.
- 3. Recursive function calls: Recursion uses additional stack memory and may make the code harder for beginners to follow initially.
- 4. May not be ideal for small arrays: Simpler sorting algorithms, such as insertion sort, can be faster for very small datasets because they have less overhead.
- 5. Not usually an in-place sort for arrays: Unlike some implementations of quick sort, standard merge sort needs temporary storage to combine elements efficiently.
Final Thoughts
Learning sorting algorithms like merge sort helps you build strong programming and problem-solving skills. By practising the merge sort code in C, understanding recursion, and analysing time complexity, you can strengthen your knowledge of data structures and algorithms. If you want to develop your programming skills through practical, project-based learning, Payilagam, a choice for learners seeking the best Software Training Institute in Chennai, can help you take the next step in your software development journey.
Frequently Asked Questions About Merge Sort in C
What Is Merge Sort in C?
Merge sort in C is a sorting algorithm that divides an array into smaller parts, sorts each part, and merges them into one sorted array. It is commonly used to arrange numbers in ascending or descending order efficiently.
Is Merge Sort a Recursive Algorithm?
Yes, merge sort is a recursive algorithm. It repeatedly calls a function to divide the array into smaller parts until each part contains one element. It then merges those parts in sorted order.
What Is the Time Complexity of Merge Sort?
The best-case, average-case, and worst-case time complexity of merge sort is \(O(n \log n)\). Its typical auxiliary space complexity is \(O(n)\) because additional memory is required during the merging process.
How Does Merge Sort Work on an Array?
Merge sort divides the array into two parts and continues splitting them into smaller sections. Once each section contains one element, the algorithm compares and merges the elements in sorted order until the entire array is sorted.
Is Merge Sort Better Than Quick Sort?
It depends on the requirements of the program. Merge sort offers predictable \(O(n \log n)\) time complexity and stable sorting, but it generally requires additional memory for arrays. Quick sort often performs well in practice and can use less auxiliary memory, but its worst-case time complexity is \(O(n^2)\) with a basic implementation. The better choice depends on the data, memory limits, and application needs.
