Merge Sort is a divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce the sorted array.
Key Concepts of Merge Sort:
- Divide:
- Split the array into two halves until each sub-array contains only one element.
- Conquer:
- Recursively sort the sub-arrays.
- Combine (Merge):
- Merge two sorted sub-arrays into a single sorted array.
Characteristics of Merge Sort:
- Time Complexity:
- Best Case: O(nlogn)O(n \log n)O(nlogn)
- Average Case: O(nlogn)O(n \log n)O(nlogn)
- Worst Case: O(nlogn)O(n \log n)O(nlogn)
- Space Complexity:
- O(n)O(n)O(n) (due to auxiliary space for merging).
- Stability:
- Merge Sort is a stable sorting algorithm, preserving the relative order of equal elements.
Steps in Merge Sort:
- Recursive Splitting:
- Divide the array into halves until the size becomes 1 (a single-element array is considered sorted).
- Merging:
- Combine two sorted arrays into a larger sorted array by comparing their elements.
Implementation of Merge Sort in C:
C Code Example:
#include <stdio.h>
// Merge function to combine two sorted halves
void merge(int arr[], int left, int mid, int right) {
int n1 = mid – left + 1; // Size of the left half
int n2 = right – mid; // Size of the right half
// Create 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];
}
// Merge the temporary arrays back into arr[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy any remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy any remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right – left) / 2;
// Recursively sort the two halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Utility function 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[] = {12, 11, 13, 5, 6, 7};
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;
}
How It Works:
Example Walkthrough:
For the array {12, 11, 13, 5, 6, 7}:
- Divide:
- Split the array into halves:
- Left half: {12, 11, 13}
- Right half: {5, 6, 7}
- Split the array into halves:
- Recursive Sorting:
- Left half:
- Split: {12} and {11, 13}
- Sort {11, 13} → {11, 13}
- Merge {12} and {11, 13} → {11, 12, 13}
- Right half:
- Split: {5} and {6, 7}
- Sort {6, 7} → {6, 7}
- Merge {5} and {6, 7} → {5, 6, 7}
- Left half:
- Merge:
- Merge {11, 12, 13} and {5, 6, 7} → {5, 6, 7, 11, 12, 13}.
Final Sorted Array:
{5, 6, 7, 11, 12, 13}
Advantages and Disadvantages:
Advantages:
- Efficient: Suitable for large datasets.
- Guaranteed O(nlogn)O(n \log n)O(nlogn) Performance: Regardless of input data order.
- Stable: Preserves relative order of equal elements.
Disadvantages:
- Auxiliary Space: Requires extra space for temporary arrays.
- Not In-Place: Memory usage can be a concern for large datasets.
Example Output:
For the input array {12, 11, 13, 5, 6, 7}:
Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
Merge Sort is a powerful and widely used algorithm, particularly for sorting linked lists and large datasets. Its divide-and-conquer approach ensures efficiency and stability.