Merge Sort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm. It divides the array into two halves, recursively sorts each half, and then merges the sorted halves. Merge Sort has a time complexity of O(n log n), making it suitable for large datasets, and it is a stable sorting algorithm, preserving the relative order of equal elements.
Understanding the Problem
The main idea of Merge Sort is to recursively divide the array until each sub-array contains a single element. Then, these sub-arrays are merged in a way that produces sorted sequences. This divide-and-conquer strategy ensures efficiency, even with large arrays, and helps avoid repeated unnecessary comparisons common in simpler algorithms like Bubble Sort.
Program: Merge Sort
This program demonstrates sorting an integer array in ascending order using the standard recursive Merge Sort algorithm.
#include <stdio.h>
#include <stdlib.h>
// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Temporary arrays
int L[n1], R[n2];
// Copy data to temporary 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 the temporary arrays 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
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Recursive merge sort function
void mergeSort(int arr[], int left, int right) {
if (left >= right)
return; // Base case: single element
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid); // Sort first half
mergeSort(arr, mid + 1, right); // Sort second half
merge(arr, left, mid, right); // Merge sorted halves
}
// Function to display array
void display(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {4, 7, 8, 1, 5, 3, 2, 6, 9};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
display(arr, size);
mergeSort(arr, 0, size - 1);
printf("Sorted array: ");
display(arr, size);
return 0;
}In this implementation, the array is recursively divided into halves until each sub-array has a single element. Then, the merge function combines the sub-arrays in sorted order. This ensures O(n log n) time complexity and stability.
FAQs
Q1: What is the time complexity of Merge Sort?
Time complexity is O(n log n) for worst, average, and best cases.
Q2: Is Merge Sort stable?
Yes, Merge Sort preserves the relative order of equal elements.
Q3: Does Merge Sort require extra memory?
Yes, temporary arrays are needed during the merge step, making its space complexity O(n).
Q4: Is Merge Sort suitable for linked lists?
Yes, Merge Sort works efficiently with linked lists, often with O(1) extra space.
Conclusion
Merge Sort is a highly efficient and stable sorting algorithm that works well with large datasets. Its divide-and-conquer approach guarantees predictable performance, and both iterative and recursive variations can be implemented. Mastering Merge Sort is essential for understanding advanced sorting and algorithmic efficiency.
References & Additional Resources
- Kernighan, Brian W., and Dennis M. Ritchie. The C Programming Language. 2nd Edition, Prentice Hall, 1988.
- Data Structures Using C by Reema Thareja – A respected textbook covering fundamental C concepts and core data structures, including the merge sort algorithm.
- Merge Sort – GeeksforGeeks – Clear explanation of merge sort using divide-and-conquer: how it splits, sorts, and merges.
- Merge Sort – Programiz – A practical guide demonstrating merge sort’s working principle, supported by examples in C and related pseudocode.
- C Program for Merge Sort – GeeksforGeeks – A complete C implementation of merge sort with explanation of the
mergeSort()andmerge()functions. - Exploring Time and Space Complexity of Merge Sort – Programiz PRO – Insightful breakdown of merge sort’s time complexity (always O(n log n)) and space requirements (O(n)), plus guidance on when the algorithm shines or falls short.
