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).