**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[100]*

**1. Algorithm:***Merge_Sort(int a[100],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[100],int low,int high,int mid)*

*Step1: Start*

*Step2: Declare integer variables and an array*

*i, j, k, c[50]*

*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**
## No comments:

## Post a Comment

Thanks

Mukesh Rajput