Merge Sort is a popular and efficient sorting algorithm based on the divide-and-conquer approach. It divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves to produce the final sorted output.
Here's a step-by-step explanation of how Merge Sort works:
- 1. Divide: The input array is divided into two equal (or almost equal) halves. This step is performed recursively until each subarray contains only one element.
- 2. Conquer: The subarrays with a single element are trivially sorted, as a single element is always considered sorted.
3. Merge: The sorted subarrays are merged back together to form larger sorted subarrays. This process continues until the entire array is merged back into a single sorted array.
The merging process is the key component of Merge Sort. To merge two sorted arrays, you compare the elements from both arrays one by one and place them in the correct order in a new temporary array. The merged array is then copied back into the original array.
Here's a high-level overview of the merge step:
- 1. Create two pointers, one for each subarray.
- 2. Compare the elements pointed by both pointers.
- 3. Choose the smaller (or larger, depending on the desired sorting order) element and add it to the merged array.
- 4. Move the pointer of the array from which the element was selected to the next element.
- 5. Repeat steps 2-4 until all elements from both subarrays are added to the merged array.
Let's see a C implementation of Merge Sort:
c#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays to store the two subarrays
int L[n1], R[n2];
// Copy data to temporary arrays
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 two temporary arrays back into arr[]
i = 0; // Initial index of the first subarray
j = 0; // Initial index of the second subarray
k = left; // 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++;
}
// 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++;
}
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // To avoid overflow for large left and right values
// Sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
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]);
}
return 0;
}Merge Sort has a time complexity of O(n log n) in the average, best, and worst cases, making it very efficient for large datasets. Additionally, Merge Sort is a stable sorting algorithm, meaning that the relative order of equal elements is preserved during the sorting process.
