# Merge sort

Merge sort methods, implementing the Merge sort
Write C programs for implementing the Merge sort methods to arrange a list of integers in ascending order.

Merge sort is based on Divide and conquer method. It takes the list to be sorted and divide it in half to create two unsorted lists. The two unsorted lists are then sorted and merged to get a sorted list. The two unsorted lists are sorted by continually calling the merge-sort algorithm; we eventually get a list of size 1 which is already sorted. The two lists of size 1 are then merged.

Properties of Merge sort method:
Best case – When the array is already sorted O(nlogn).
Worst case – When the array is sorted in reverse order O(nlogn).
Average case – O(nlogn).
Extra space is required, so space complexity is O(n) for arrays and O(logn) for linked lists.

Merge sort algorithm:
Globally declaring array int a

1. Algorithm:
Merge_Sort(int a,int low,int high)
Step1: Start
Step2: Declare an integer middle variable int mid
Step3: Check the condition low less than high
if(low<high)
Step4: Initialize mid
mid=(low+high)/2
Step5: call sub_function mergsort from low to middle
Merge_Sort (a,low,mid)
Step6: call sub_function mergsort from middle+1 to high
Merge_Sort (a, mid+1,high)
Step7: call sub_function Merg from low to high
Merge (a,low,high,mid)
Step8: Stop

2. Algorithm:
Merge (int a,int low,int high,int mid)
Step1: Start
Step2: Declare integer variables and an array
i, j, k, c
Step3: Initialize i to low
i=low
Step4: Initialize j to mid +1
j=mid+1
Step5: Initialize k to low
k=low
Step6: Repeat Step(a) to Step(c) upto while((i<=mid)&&(j<=high))
a) Check (a) upto an array a[i] less than a[j] otherwise (b)
if(a[i]<a[j])
c[k]=a[i]
i++
k++
b) Otherwise
c[k]=a[j]
j++
k++
c) Repeat upto while (i<=mid)
c[k]=a[i];
i++;
k++;
Step7: Repeat a to b until while(j<=high)
a) c[k]=a[j];
b) j++;
c) k++;
Step8: Repeat until for(i=0;i<k;i++)
a[i]=c[i]
Step9: stop

3. Algorithm:
main ()
Step1: Start
Step2: Declare integer variables i, n
Step3: Read the size / no. of elements
Step4: Read the array elements a[i]
Step5: call the sub_function Merge_Sort (a, 0, n-1)
Step6: Print the sorted array: a[i]

Thanks
Mukesh Rajput Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..

Thanks
Mukesh Rajput