Index
Merge Sort
Merge Sort is a comparison-based sorting algorithm that follows the Divide and Conquer strategy. It divides the unsorted array into two halves, sorts each half independently, and then merges the sorted halves to produce the final sorted array.
Here’s how the Merge Sort algorithm works:
- Divide: Divide the unsorted array into two halves.
- Conquer: Recursively sort the two halves.
- Merge: Merge the two sorted halves to produce a single sorted array.
Here’s a high-level description of the Merge Sort algorithm:
- If the array has zero or one element, it is already sorted.
- If the array has more than one element, recursively divide the array into two halves.
- Recursively sort each half.
- Merge the sorted halves back together.
#include <stdio.h>
#include <stdlib.h>
// Merge two sorted subarrays arr[l..m] and 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;
j = 0;
k = l;
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++;
}
}
// Merge Sort function
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // Find the middle point
// Recursively sort the first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
// Print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test Merge Sort
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("\nSorted array: \n");
printArray(arr, n);
return 0;
}
Output:
Original array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13
Time Complexity
The time complexity of Merge Sort is O(nlogn), where n is the number of elements in the array.
Here’s why:
- Divide and Conquer Approach: Merge Sort follows the Divide and Conquer strategy. It divides the array into halves recursively until it gets down to single-element subarrays. Then, it merges these subarrays in a sorted manner.
- Recursive Nature: The algorithm splits the array in half at each level of recursion. As a result, it requires O(logn) levels of recursion to sort the array.
- Merging Step: At each level of recursion, the algorithm merges two sorted subarrays of size n/2. Merging two sorted arrays of size n/2 takes O(n) time.
The recurrence relation for the time complexity of Merge Sort can be expressed as follows:
T(n)=2T(n/2)+O(n)
By using the Master Theorem or by expanding the recurrence, we find that the time complexity is O(nlogn).
