Merge Sort Algorithm

What is Sorting?

Sorting refers to arranging data in a particular format. The sorting algorithm specifies the way to.
arrange data in a particular order.
Sorting is nothing but storage of data in sorted order, Types of Sorting descending
order.
Sorting arranges data in a sequence which makes searching easier.

Complexity of Sorting algorithm

The complexity of the sorting algorithm calculates the running time of a function in which ‘n’ number of items is to be sorting.
So, The choice for which sorting method is suitable for a problem depends on several dependencies.
Then, Configurations for different problems.
So, The most noteworthy of these considerations are:
Moreover, The length of time spent by the programmer in.
So, Programming a specific sorting program.
Then, the Amount of machine time necessary for running the program.
At the last, The amount of memory necessary for running the program.

Types of Sorting

1. Selection Sort
2. Bubble sort
3. Insertion sort
4. Quick Sort
5. Shell Sort
6. Merge Sort etc.

Merge Sort Algorithm

Divide And Conquer

Merging two lists of one element each is the same as sorting them.
Merge sort divides up an unsorted list until the above condition is met and then sorts the divided parts back together in pairs.
Specifically, this can be done by recursively dividing the unsorted list in half, merge sorting the left side then the right side, and then merging the left and right back together

Divide-and-conquer Technique For Merge Sort Algorithm

Using Divide and Conquer: Merge sort Algorithm strategy

Merge Sort Algorithm

Divide: Partition ‘n’ elements array into two 
sub lists with n/2 elements each
• Conquer: Sort sub list1 and sub list2
• Combine: Merge sub list1 and sub list2

Then, Using C programming to perform this sorting operation you can follow any language.

So, try it your self on online compiler.

/* Function to print an array */
void printArray(int A[], int size) 
{ 
 int i; 
 for (i=0; i < size; i++) 
 printf("%d ", A[i]); 
 printf("\n"); 
} 
/* Driver program to test above functions */
int main() 
{ 
 int arr[] = {12, 11, 13, 5, 6, 7}; 
 int arr_size = sizeof(arr)/sizeof(arr[0]); 
 printf("Given array is \n"); 
 printArray(arr, arr_size); 
 mergeSort(arr, 0, arr_size - 1); 
 printf("\nSorted array is \n"); 
 printArray(arr, arr_size); 
 return 0; 
}
// Merges 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 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]; 
 i++; 
 k++; 
 } 
 /* Copy the remaining elements of R[], if 
there are any */
 while (j < n2) 
 { 
 arr[k] = R[j]; 
 j++; 
 k++; 
 } 
} 
/* l is for left index and r is right index of 
the sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
 if (l < r) 
 { 
 // Same as (l+r)/2, but avoids overflow for 
 // large l and h 
 int m = l+(r-l)/2; 
 
 // Sort first and second halves 
 mergeSort(arr, l, m); 
 mergeSort(arr, m+1, r); 
 
 merge(arr, l, m, r); 
 } 
}

Time Complexity Analysis

Worst case: O(nlog₂n)
Average case: O(nlog₂n​)
Best case: O(nlog₂n​

Than, If you want to read more …….

so, visit our website and click here:-https://learningpoints.in/

And for more algorithm concept click on- Algorithm Archives – Learning Points

thank you for coming to our website please share with your friends And do comment

Thank you.