Merge Sort
Merge Sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or list. Merge Sort works by recursively dividing an array or list into smaller sub-arrays until each sub-array contains only one element (which is trivially sorted). Then, it repeatedly merges these smaller sorted sub-arrays to produce a larger, sorted array. It's efficient and stable, with a time complexity of O(n log n) in the worst, average, and best cases. Here's a detailed algorithm for Merge Sort.
Divide: Divide the unsorted list into two sublists of about equal size. You can do this by finding the middle point of the list.
Divide the unsorted array into two halves.Find the middle of the array by calculating
middle = (start + end) // 2, where start is the index of the first element, and end is the index of the last element.
Conquer: Recursively sort both sublists. This is done by applying the merge sort algorithm to each sublist until they become smaller sublists or single elements (base case).
Apply the Merge Sort algorithm to the left half of the array, i.e., the portion from start to middle.
Apply the Merge Sort algorithm to the right half of the array, i.e., the portion from middle + 1 to end.
Merge: Merge the two sorted sublists back into a single sorted list. This is the "conquer" step, where you combine the sublists while maintaining the sorted order.
Merge the sorted halves to create a single sorted array.Create two pointers, one for each half (e.g., left_ptr for the left half and right_ptr for the right half).
Compare the elements at the current positions of the two pointers and select the smaller element to add to the merged array.Move the pointer of the selected element to the next position.
Repeat the comparison and addition until you have merged all elements from both halves into a single sorted array.
Repeat steps 1 to 3 recursively for each sub-array until the entire array is sorted.
Example:
Let's use a simple example to illustrate the merge sort algorithm. Suppose we have an unsorted list
[38, 27, 43, 3, 9, 82, 10].
Split the list into two halves: [38, 27, 43] and [3, 9, 82, 10].
Recursively sort both halves:
Left half: [27, 38, 43]
Right half: [3, 9, 10, 82]
Merge the two sorted halves:Merge [27, 38, 43] and [3, 9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82].
So, the sorted list is [3, 9, 10, 27, 38, 43, 82], which is the correct result.
Right half: [3, 9, 10, 82]
Merge the two sorted halves:Merge [27, 38, 43] and [3, 9, 10, 82] to get [3, 9, 10, 27, 38, 43, 82].
So, the sorted list is [3, 9, 10, 27, 38, 43, 82], which is the correct result.
Pseudo Code
merge_sort(arr, left, right)
if left < right:
mid = (left + right) / 2
merge_sort(arr, left, mid) // Recursively sort left half
merge_sort(arr, mid + 1, right) // Recursively sort right half
merge(arr, left, mid, right) // Merge the two sorted halves
merge(arr, left, mid, right)
n1 = mid - left + 1
n2 = right - mid
// Create temporary arrays
left_half[n1], right_half[n2]
// Copy data to temporary arrays left_half[] and right_half[]
for i = 0 to n1 - 1:
left_half[i] = arr[left + i]
for j = 0 to n2 - 1:
right_half[j] = arr[mid + 1 + j]
// Merge the temporary arrays back into arr[left..right]
i = 0
j = 0
k = left
while i < n1 and j < n2:
if left_half[i] <= right_half[j]:
arr[k] = left_half[i]
i++
else:
arr[k] = right_half[j]
j++
k++
// Copy the remaining elements of left_half[], if any
while i < n1:
arr[k] = left_half[i]
i++
k++
// Copy the remaining elements of right_half[], if any
while j < n2:
arr[k] = right_half[j]
j++
k++
Best Case: O(n log n) - Merge Sort divides the input array into two halves recursively until it reaches sub-arrays of size 1 or 0. The merging step takes O(n) time in each level of recursion, and there are log₂(n) levels of recursion, resulting in a best-case time complexity of O(n log n).
Average Case: O(n log n) - Merge Sort's average-case time complexity is the same as its best-case time complexity. It consistently divides the input in half and merges the sub-arrays, leading to O(n log n) time.
Worst Case: O(n log n) - Merge Sort's worst-case time complexity is also O(n log n). This is because, in each level of recursion, the input is divided in half, and even in the worst-case scenario, merging two sub-arrays takes O(n) time.
Space Complexity:
Merge Sort has a space complexity of O(n) due to the additional memory required to store temporary sub-arrays during the merging process. Specifically, for each level of recursion, temporary arrays of size n are created, and there are log₂(n) levels of recursion. Therefore, the space complexity is O(n) for the additional memory used during the sorting process.
In practice, this means that Merge Sort is not an in-place sorting algorithm (unlike algorithms like Quick Sort), as it requires additional memory proportional to the size of the input array. However, it is a stable and efficient sorting algorithm, making it a good choice when memory usage is not a primary concern.
C Program - Merge Sort
/*******************************************************************************/
#include <stdio.h>
// Function to merge two subarrays of arr[]
// First subarray is arr[l..m]
// Second subarray is 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 there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function to perform merge sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
int main() {
int arr[50],n,i;
printf("Enter size of the array: ");
scanf("%d",&n);
printf("Enter %d elements: ",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
mergeSort(arr, 0, n - 1);
printf("\nSorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Comments
Post a Comment