Welcome back to our C Language Series! In this installment, #132, we dive deep into one of the most efficient and widely used sorting algorithms: Merge Sort. Known for its stability and guaranteed performance, Merge Sort is a fundamental algorithm every C programmer should understand.
Understanding Merge Sort: The Divide and Conquer Approach
Merge Sort is a classic example of a Divide and Conquer algorithm. It tackles a large problem by breaking it down into smaller, more manageable subproblems, solving those subproblems, and then combining their solutions to solve the original problem.
Here's how it generally works:
- Divide: The unsorted list is divided into n sublists, each containing one element (a list of one element is considered sorted).
- Conquer (Recursion): Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
- Combine (Merge): The core operation. Two smaller sorted sublists are merged to form a larger sorted sublist.
How Merge Sort Works Step-by-Step
Let's illustrate with an example array: [38, 27, 43, 3, 9, 82, 10]
-
Divide: The array is split into two halves recursively until individual elements are reached.
- Initial array:
[38, 27, 43, 3, 9, 82, 10] - First division:
[38, 27, 43, 3]and[9, 82, 10] - Further division until single elements:
[38],[27],[43],[3],[9],[82],[10]
- Initial array:
-
Merge: Now, these single-element lists are merged back in sorted order.
- Merge
[38]and[27]→[27, 38] - Merge
[43]and[3]→[3, 43] - Merge
[9]and[82]→[9, 82] [10]remains as is.- Then, merge
[27, 38]and[3, 43]→[3, 27, 38, 43] - And merge
[9, 82]and[10]→[9, 10, 82] - Finally, merge
[3, 27, 38, 43]and[9, 10, 82]→[3, 9, 10, 27, 38, 43, 82]
- Merge
Implementing Merge Sort in C
The implementation involves two primary functions: mergeSort() which handles the recursive splitting, and merge() which performs the crucial combining of two sorted subarrays.
1. The merge() Function
This function takes two sorted subarrays and merges them into a single sorted array. It's the heart of the algorithm. We'll need temporary arrays to hold the merged elements during the process.
#include <stdio.h>
#include <stdlib.h> // For malloc and free
// Merges two subarrays of arr[].
// First subarray is arr[left..mid]
// Second subarray is arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays L[] and R[]
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
// Check for malloc failure (good practice for robust code)
if (L == NULL || R == NULL) {
fprintf(stderr, "Memory allocation failed in merge!\n");
// Proper error handling might involve exiting or returning an error code
if (L != NULL) free(L);
if (R != NULL) free(R);
return;
}
// Copy data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
L[i] = arr[left + i];
for (j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr[left..right]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = left; // 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 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++;
}
// Free the dynamically allocated temporary arrays
free(L);
free(R);
}
2. The mergeSort() Function
This is the recursive function that continuously divides the array into halves until individual elements are reached, and then calls the merge() function to combine them in sorted order.
// Main function that sorts arr[left..right] using merge()
void mergeSort(int arr[], int left, int right) {
if (left < right) {
// Calculate mid to avoid overflow for large 'left' and 'right'
// (left + right) / 2 could overflow if left and right are very large,
// (left + (right - left) / 2) is safer.
int mid = left + (right - left) / 2;
// Sort first and second halves recursively
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
3. Utility Function: printArray()
A simple helper function to display the contents of an array, useful for testing and debugging.
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
4. Putting it all together: main() function
Here's how you can integrate and use mergeSort() in your C program:
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("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
When you run the above main function, you will see the unsorted and then the sorted array printed to the console.
Time and Space Complexity of Merge Sort
Understanding the performance characteristics is crucial for any algorithm.
Time Complexity
- Best Case: O(N log N)
- Average Case: O(N log N)
- Worst Case: O(N log N)
Merge Sort consistently performs in O(N log N) time regardless of the initial order of elements. This is because it always divides the array into two halves and merges them, performing roughly the same number of operations regardless of data distribution. The recurrence relation is T(N) = 2T(N/2) + O(N), where O(N) represents the work done in the merge operation.
Space Complexity
- Auxiliary Space: O(N)
Merge Sort requires O(N) auxiliary space because of the temporary arrays (L and R) created during the merge operation. While in-place merge sort algorithms exist, they are significantly more complex to implement and often have higher constant factors for time complexity, making the standard implementation more practical in many scenarios.
Advantages and Disadvantages of Merge Sort
Advantages
- Stable: It maintains the relative order of equal elements, which is important in specific applications.
- Guaranteed Performance: Consistent O(N log N) time complexity in all cases (best, average, worst), making it predictable.
- Effective for Large Data: Well-suited for sorting large datasets, especially those that don't fit into memory (known as external sorting).
- Parallelizable: The divide step makes it relatively easy to parallelize the sorting of sub-arrays, leveraging multi-core processors.
Disadvantages
- Space Complexity: Requires O(N) auxiliary space, which can be a concern for very large datasets on systems with limited memory.
- Slower for Small Data: Due to the overhead of recursion and temporary array creation, it can be slower than simpler algorithms like Insertion Sort for very small arrays, where constant factors matter more than asymptotic complexity.
- Not In-Place: The standard implementation is not an in-place sort, meaning it requires additional memory proportional to the input size.
Conclusion
Merge Sort is a powerful and reliable sorting algorithm, a cornerstone of computer science education and practical applications. Its consistent O(N log N) performance and stability make it an excellent choice for many scenarios, particularly when dealing with large datasets or when maintaining element order is a requirement. While it comes with an O(N) space overhead, its benefits often outweigh this consideration in modern systems.
Mastering Merge Sort deepens your understanding of recursive algorithms and the Divide and Conquer paradigm. We encourage you to experiment with the C code provided, modify it, and observe its behavior. Happy coding!