Saturday 15 September 2012

Program to implement the merge sort method


Description:
The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list. Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).
Algorithm: main program
Step1: Start
Step2: declare the merge sort function
Step3: Declare the array and their size and initailaze the j=0
Step4: read the array elements and then sort these elements.
Step5: read the array elements before the merge sort and then display the   
           elements.
Step6: call the merge sort function
Step7: display the array elements after merge sort by using the following stament.
            for( j=0;j<Max_ary;j++)
Step8: Stop
Subprogram
Step1:initialize the array excuting[MAX_ARY] and 
           j=0,mid=0,mrg1=0,mrg2=0,size=start-end+1
Step2: check the condition if(end==start) then return
Step3: calculate the mid value
             Mid=(end+start)/2
Step4: call themerge_sort(x,end,mid)
Step5:merge_sort(x,mid+1,start)
Step6: performing the looping operation
             For(j=0;j<SIZE;j++) then its true
             Executing[j]=x[end+1]
Mrg1=0;
Step7: calculate the mrg2=mid-end+1
Step8: performing the looping operation
             For(j=0;j<SIZE;j++) then its true then goto step9
Step9: check the condition
i)                    if(mrg2<=start-end) is true goto ii). If not goto Step12.
ii)                  If(mrg1<=mid-end) is true goto iii). If not goto step11
iii)                If(executing[mrg1]>executing[mrg2]) is true then follows. If not goto step10.
X[j+end]= executing[mrg2++]
Step10: x[j+end]=executing[mrg1++]. If not goto Step11
Step11: x[j+end]= executing[mrg2++]
Step12: x[j+end]=executing[mrg1++]
Step13: return to main program
Program:
#include <stdio.h>
#include <stdlib.h>

#define MAX_ARY 10

void merge_sort(int x[], int end, int start);

int main(void) {
 int ary[MAX_ARY];
 int j = 0;

 printf("\n\nEnter the elements to be sorted: \n");
   for(j=0;j<MAX_ARY;j++)
       scanf("%d",&ary[j]);

 /* array before mergesort */
 printf("Before    :");
 for(j = 0; j < MAX_ARY; j++)
  printf(" %d", ary[j]);

 printf("\n");

 merge_sort(ary, 0, MAX_ARY - 1);

 /* array after mergesort */
 printf("After Merge Sort :");
 for(j = 0; j < MAX_ARY; j++)
  printf(" %d", ary[j]);

 printf("\n");
 getch();
}

/* Method to implement Merge Sort*/
void merge_sort(int x[], int end, int start) {
int j = 0;
 const int size = start - end + 1;
 int mid  = 0;
 int mrg1 = 0;
 int mrg2 = 0;
 int executing[MAX_ARY];

 if(end == start)
  return;

 mid  = (end + start) / 2;

 merge_sort(x, end, mid);
 merge_sort(x, mid + 1, start);

 for(j = 0; j < size; j++)
  executing[j] = x[end + j];

 mrg1 = 0;
 mrg2 = mid - end + 1;

 for(j = 0; j < size; j++) {
  if(mrg2 <= start - end)
   if(mrg1 <= mid - end)
    if(executing[mrg1] > executing[mrg2])
     x[j + end] = executing[mrg2++];
    else
     x[j + end] = executing[mrg1++];
   else
    x[j + end] = executing[mrg2++];
  else
   x[j + end] = executing[mrg1++];
 }
}
Output:
Enter the elements to be sorted:
8 2 3 4 1 5 7 6 9 0
Before    : 8 2 3 4 1 5 7 6 9 0
After Merge Sort : 0 1 2 3 4 5 6 7 8 9

Enter the elements to be sorted:
7 6 5 4 8 4 3 2 1 3
Before    : 7 6 5 4 8 4 3 2 1 3
After Merge Sort : 1 2 3 3 4 4 5 6 7 8
Conclusion: the program is error free
VIVA QUESATIONS
1) Define merge sort ?
Ans: The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list.
2) Efficiency of merge sort ?
Ans: O(n log n).


No comments:

Post a Comment