Simple implementation of the Merge Sort algorithm in C
#include <stdio.h>
// Merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// Merge the temporary arrays back into arr[l..r]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function to perform Merge Sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m = l + (r - l) / 2;
// Sort the first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("Sorted array is \n");
printArray(arr, arr_size);
return 0;
}
let’s break down the code for the Merge Sort algorithm in C step by step
#include <stdio.h>
This line includes the standard input/output library for basic I/O operations like printf.
void merge(int arr[], int l, int m, int r) {
Here, we define the merge function, which takes an array arr[] and three integer parameters: l (left index), m (middle index), and r (right index). This function is responsible for merging two sorted subarrays, one from l to m and the other from m+1 to r.
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temporary arrays
int L[n1], R[n2];
We declare variables i, j, and k for iterating through the subarrays. We also calculate the sizes of the two subarrays, n1 and n2. Two temporary arrays, L and R, are created to hold the elements of the subarrays.
// Copy data to temporary arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
In these loops, we copy the elements of the original array arr[] into the temporary arrays L[] and R[]. This step separates the original array into two sorted subarrays.
// Merge the temporary arrays back into arr[l..r]
i = 0; // Initial index of the first subarray
j = 0; // Initial index of the second subarray
k = l; // Initial index of the merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
In this section, we merge the two sorted subarrays back into the original array arr[]. The while loop compares elements from L[] and R[], copying the smaller element into arr[] and incrementing the respective indices. This process continues until we have merged all elements.
// Copy the remaining elements of L[], if any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
These two while loops handle any remaining elements in L[] and R[]. If there are elements left in either subarray, they are copied into the original array arr[].
}
void mergeSort(int arr[], int l, int r) {
Now, we define the mergeSort function, which takes the array arr[], the left index l, and the right index r as parameters. This function performs the Merge Sort algorithm recursively.
if (l < r) {
The function checks if the left index l is less than the right index r. If this condition is met, it means there is more than one element in the subarray, so we proceed with sorting.
int m = l + (r - l) / 2;
Here, we calculate the middle index m to divide the array into two halves.
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
We recursively call mergeSort on the left and right halves of the array, effectively dividing the problem into smaller subproblems.
merge(arr, l, m, r);
}
}
After sorting the subarrays, we use the merge function to merge them back together in sorted order.
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
This function, printArray, is used to print the elements of an array for demonstration purposes.
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("Sorted array is \n");
printArray(arr, arr_size);
return 0;
}
In the main function, we initialize an array with unsorted elements. We then call mergeSort to sort the array, and finally, we print both the original and sorted arrays.
This code provides a working example of the Merge Sort algorithm in C, demonstrating the core concepts of the algorithm, including the divide-and-conquer approach and merging of sorted subarrays.
1. Understanding Merge Sort:
- Merge Sort is a sorting algorithm based on the divide-and-conquer strategy. It works by recursively dividing an array into two halves, sorting each half, and then merging the sorted halves back together.
- The algorithm maintains stability, meaning that equal elements retain their relative order in the sorted output.
- Merge Sort is advantageous for large datasets because it guarantees a time complexity of O(n log n) in all cases, making it more efficient than some other sorting algorithms like Bubble Sort or Insertion Sort.
2. Algorithm Implementation in C:
- In C, Merge Sort can be implemented using recursion. The key idea is to divide the array into smaller subarrays until each subarray contains only one element (the base case). Then, merge these subarrays back together while maintaining their sorted order.
- The recursive implementation involves breaking down the problem into smaller, more manageable subproblems, which is a hallmark of the divide-and-conquer approach.
3. Merging Two Sorted Arrays:
- Merging two sorted arrays is a crucial step in Merge Sort. It involves comparing elements from two sorted subarrays and merging them into a single sorted array.
- This process requires creating an auxiliary array to temporarily store the merged elements.
- The merge step ensures that the elements from the original array are sorted correctly.
4. Time Complexity Analysis:
- Merge Sort exhibits a time complexity of O(n log n), where ‘n’ is the number of elements to be sorted.
- The algorithm consistently performs well and does not degrade to worst-case scenarios like some other sorting algorithms.
- It is particularly efficient for sorting large datasets or in situations where stability is essential.
5. Space Complexity and Optimization:
- Merge Sort typically has a space complexity of O(n) because it requires additional memory for the temporary arrays used during merging.
- To optimize space usage, in-place Merge Sort can be implemented, which reduces the auxiliary space requirement.
- In-place Merge Sort is more memory-efficient but may be slightly slower due to increased element shifting during merging.
6. Stability and Applications:
- Merge Sort is considered a stable sorting algorithm because it preserves the relative order of equal elements.
- Stability is crucial in various real-world applications, such as database sorting, where maintaining the original order of records is essential for correct results.
- Merge Sort’s stability makes it a preferred choice in these scenarios.
7. Coding Merge Sort: A Step-by-Step Tutorial:
- In this section, readers are guided through the step-by-step process of coding Merge Sort in the C programming language.
- Topics covered include breaking down the problem into smaller steps, implementing the recursive merge sort function, and merging sorted subarrays.
8. Handling Edge Cases and Performance Tips:
- This section addresses specific scenarios where Merge Sort can be applied, such as sorting linked lists or custom data structures.
- Performance tips and best practices, such as optimizing the choice of sorting algorithm for different input sizes, are discussed.
9. Visualizing Merge Sort:
- Tools and resources for visualizing Merge Sort are introduced. Visualization helps learners grasp how data elements are rearranged at each step of the sorting process, making the algorithm’s behavior more understandable.
10. Comparing Merge Sort Variants:
Variants of Merge Sort, such as Bottom-Up Merge Sort and Three-Way Merge Sort, are explored. – Differences between these variants, along with their use cases, are discussed to provide readers with a comprehensive view of Merge Sort options.
In conclusion, this article covers a wide range of topics related to Merge Sort in C, from its fundamental principles and implementation details to its applications and optimization techniques. Whether you are a beginner looking to understand sorting algorithms or an experienced programmer seeking to implement Merge Sort effectively, this comprehensive guide provides valuable insights and practical knowledge.