MERGE SORT :
MERGE Sort IS a popular AND efficient sorting algorithm that follows
the divide-and-conquer approach TO sort an array OR list OF elements.
It divides the INPUT INTO smaller parts, sorts them individually, AND
THEN merges the sorted parts TO obtain the final sorted RESULT.
The TIME complexity OF MERGE Sort IS O(n log n), making it one OF
the fastest sorting algorithms FOR LARGE datasets.
Here's a high-level description of the Merge Sort algorithm:
1. *Divide*: The unsorted array is divided into two halves.
This step continues recursively until the sub-arrays contain only
one element, which is inherently sorted.
2. **Conquer (Sort)**: Each sub-array is sorted individually either by
applying Merge Sort again on them or using a different sorting algorithm,
like Insertion Sort or Bubble Sort, for small enough sub-arrays.
3. **Combine (Merge)**: The sorted sub-arrays are merged together to create
larger sorted arrays. This merging process combines the elements from both
sub-arrays in a way that maintains the sorted order.
```Algorithm Of Merge Sort.
MergeSort(arr, left, right):
if left < right:
middle = (left + right) / 2
MergeSort(arr, left, middle)
MergeSort(arr, middle + 1, right)
Merge(arr, left, middle, right)
Merge(arr, left, middle, right):
n1 = middle - left + 1
n2 = right - middle
leftArr[n1], rightArr[n2]
for i = 0 to n1 - 1:
leftArr[i] = arr[left + i]
for j = 0 to n2 - 1:
rightArr[j] = arr[middle + 1 + j]
i = 0, j = 0, k = left
while i < n1 and j < n2:
if leftArr[i] <= rightArr[j]:
arr[k] = leftArr[i]
i++
else:
arr[k] = rightArr[j]
j++
k++
while i < n1:
arr[k] = leftArr[i]
i++
k++
while j < n2:
arr[k] = rightArr[j]
j++
k++
Keep in mind that Merge Sort is generally considered a stable sorting algorithm
(maintains the relative order of equal elements) and is suitable for large datasets
due to its efficient time complexity.
Sure! Let's walk through an example OF MERGE Sort step BY step TO understand how it works.
We'll use the following unsorted array:
Sure! Let's sort the given unsorted array [7, 3, 2, 16, 24, 4, 11, 9]
USING the MERGE Sort algorithm.
Step 1: Divide
--------------
1. Divide the array INTO two halves:
- LEFT half: [7, 3, 2, 16]
- RIGHT half: [24, 4, 11, 9]
2. Divide the LEFT half INTO two more halves:
- LEFT half: [7, 3]
- RIGHT half: [2, 16]
3. Continue dividing the sub-arrays until each one contains ONLY one element.
Step 2: Sort (Conquer)
-------------------------
1. Sort the leftmost sub-arrays:
- [7, 3] (sort USING MERGE sort TO GET [3, 7])
- [2, 16] (sort USING MERGE sort TO GET [2, 16])
2. Sort the rightmost sub-arrays:
- [24, 4] (sort USING MERGE sort TO GET [4, 24])
- [11, 9] (sort USING MERGE sort TO GET [9, 11])
Step 3: MERGE (Combine)
--------------------------
1. MERGE the two leftmost sub-arrays [3, 7] AND [2, 16]:
- Compare 3 AND 2, pick 2, move TO the NEXT element IN the RIGHT array.
- Compare 3 AND 16, pick 3, move TO the NEXT element IN the LEFT array.
- Since the LEFT array IS exhausted, append the remaining elements FROM
- the RIGHT array ([16]).
RESULT: [2, 3, 7, 16]
2. MERGE the two rightmost sub-arrays [4, 24] AND [9, 11]:
- Compare 4 AND 9, pick 4, move TO the NEXT element IN the LEFT array.
- Compare 9 AND 24, pick 9, move TO the NEXT element IN the RIGHT array.
- Since the RIGHT array IS exhausted, append the remaining elements FROM
- the LEFT array ([11]).
RESULT: [4, 9, 11, 24]
3. Finally, MERGE the two merged sub-arrays [2, 3, 7, 16] AND [4, 9, 11, 24]:
- Compare 2 AND 4, pick 2, move TO the NEXT element IN the LEFT array.
- Compare 3 AND 4, pick 3, move TO the NEXT element IN the LEFT array.
- Compare 4 AND 7, pick 4, move TO the NEXT element IN the LEFT array.
- Compare 7 AND 9, pick 7, move TO the NEXT element IN the LEFT array.
- Compare 9 AND 11, pick 9, move TO the NEXT element IN the LEFT array.
- Compare 11 AND 16, pick 11, move TO the NEXT element IN the LEFT array.
- Compare 16 AND 24, pick 16, move TO the NEXT element IN the LEFT array.
- Since the LEFT array IS exhausted, append the remaining elements FROM
- the RIGHT array ([24]).
RESULT: [2, 3, 4, 7, 9, 11, 16, 24]
The final sorted array IS [2, 3, 4, 7, 9, 11, 16, 24], AND the MERGE Sort algorithm IS
complete.
AS you can see, MERGE Sort divides the problem INTO smaller parts, sorts them individually,
AND THEN merges them TO obtain the final sorted array.
Program of Merge sort Using C language.
#include <stdio.h>
// Merge two sorted subarrays into one sorted array
void merge(int arr[], int left, int middle, int right) {
int left_size = middle - left + 1;
int right_size = right - middle;
int left_array[left_size];
int right_array[right_size];
// Copy data to temporary arrays
for (int i = 0; i < left_size; i++)
left_array[i] = arr[left + i];
for (int j = 0; j < right_size; j++)
right_array[j] = arr[middle + 1 + j];
// Merge the two temporary arrays back into arr
int i = 0, j = 0, k = left;
while (i < left_size && j < right_size) {
if (left_array[i] <= right_array[j]) {
arr[k] = left_array[i];
i++;
} else {
arr[k] = right_array[j];
j++;
}
k++;
}
// Copy any remaining elements of left_array and right_array
while (i < left_size) {
arr[k] = left_array[i];
i++;
k++;
}
while (j < right_size) {
arr[k] = right_array[j];
j++;
k++;
}
}
// Merge Sort function
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int middle = left + (right - left) / 2;
// Sort the first and second halves separately
merge_sort(arr, left, middle);
merge_sort(arr, middle + 1, right);
// Merge the sorted halves
merge(arr, left, middle, right);
}
}
// Function to print an array
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
print_array(arr, size);
merge_sort(arr, 0, size - 1);
printf("Sorted array: ");
print_array(arr, size);
return 0;
}
OUTPUT :
Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82
