Thursday, 28 December 2017

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