1.Merge Sort Algorithm Overview
Merge Sort is a Divide and Conquer algorithm for sorting
an array.
Divide and Conquer Technique in Merge
Sort
InMerge Sort, the array is divided into two halves, sorted
separately and then merged. This process is repeated for
each half until there are no more elements to divide.
Merge Function in Merge Sort
The merge function is a crucial part of Merge Sort. It takes
two sorted arrays as input, merges them and returns a
single array which is also sorted.
Merging Sorted Sublists in Merge Sort
The Merge function works on the principle of merging two
sorted sublists. It iterates through each sublist and
compares the smallest elements. The smallest element is
then added to the output array and the process is
continued until one sublist is empty.
Handling Remaining Elements in Sublists
Once one of the sublists is empty, the remaining elements
in the other sublist are added to the output array in the
same order.
Copying Sorted Elements to Original Array
After the two halves have been sorted and merged, the
sorted elements are copied back to the original array.
,Time Complexity of Merge Function
The time complexity of the Merge function is O(n), where
n is the number of elements in the input array.
Time Complexity of Merge Sort
The time complexity of Merge Sort is O(n log n) due to the
divide and conquer nature of the algorithm.
Merge Function Logic and Implementation
Here's a sample implementation of the Merge Function:
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// create temp arrays
int L[n1], R[n2];
// Copy data to temp 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 temp arrays back into arr[l..r]
, i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of 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
there are any
while (i < n1)
{
arr[k] = L[i];
Merge Sort is a Divide and Conquer algorithm for sorting
an array.
Divide and Conquer Technique in Merge
Sort
InMerge Sort, the array is divided into two halves, sorted
separately and then merged. This process is repeated for
each half until there are no more elements to divide.
Merge Function in Merge Sort
The merge function is a crucial part of Merge Sort. It takes
two sorted arrays as input, merges them and returns a
single array which is also sorted.
Merging Sorted Sublists in Merge Sort
The Merge function works on the principle of merging two
sorted sublists. It iterates through each sublist and
compares the smallest elements. The smallest element is
then added to the output array and the process is
continued until one sublist is empty.
Handling Remaining Elements in Sublists
Once one of the sublists is empty, the remaining elements
in the other sublist are added to the output array in the
same order.
Copying Sorted Elements to Original Array
After the two halves have been sorted and merged, the
sorted elements are copied back to the original array.
,Time Complexity of Merge Function
The time complexity of the Merge function is O(n), where
n is the number of elements in the input array.
Time Complexity of Merge Sort
The time complexity of Merge Sort is O(n log n) due to the
divide and conquer nature of the algorithm.
Merge Function Logic and Implementation
Here's a sample implementation of the Merge Function:
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// create temp arrays
int L[n1], R[n2];
// Copy data to temp 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 temp arrays back into arr[l..r]
, i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of 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
there are any
while (i < n1)
{
arr[k] = L[i];
