Merge Sorting

7. Program to sort an array using Merge Sorting?

Algorithm

Globally,Declare the array,a[10].

Step 1:Start

Step 2:Declare variables low,high,n,i.

Step 3:Input and read the array size,n.

Step 4:Input and read the elements of the array.

Step 5:Initialize low=0,high=n-1.

Step 6:Call the function mergesrt(low,high).

Step 7:Print the sorted array.

Step 8:Stop.

Function mergesrt(low,high)

Step 1:Declare variable mid.

Step 2:If low!=high then

                   2.1)Find mid=(low+high)/2.

                   2.2)Call the function mergesrt(low,mid).

                   2.3)Call the function mergesrt(mid+1,high).

                   2.4)Call the function merge(low,mid,high).

Step 3:End if.

Step 4:Return.

Function merge(low,mid,high)

Step 1:Declare the temp[10].

Step 2:Declare variables i,j,k.

Step 3:Assign i=low,j=mid+1 and k=low.

Step 4: while(i<=mid) and (j<=high) repeat steps 4.1 to 4.3

                   4.1) if(a[i]<=a[j]) then

                             a)Copy the number,a[i] to the array,temp;temp[k]=a[i]

                             b)Increment i and k by 1.

                   4.2)Else

                             a) Copy the number,a[j] to the array,temp;temp[k]=a[j]

                             b)Increment j and k by 1.

                   4.3)End if.

Step 5:End while.

Step 6:while (i<=mid) repeat steps 6.1 and 6.2

                   6.1)temp[k]=a[i]

                   6.2) Increment i and k by 1.

Step 7:End while.

Step 8: while (j<=high) repeat steps 8.1 and 8.2

                   8.1)temp[k]=a[j]

                   8.2) Increment j and k by 1.

Step 9:End while.

Step 10:Initialize i as low.

Step 11:while(i<=high) repeat steps 11.1 and 11.2

                   11.1)Assign a[i]=temp[i].

                   11.2)Increment i by 1.

Step 12:End while.

Step 13:Return.

Program

#include<conio.h>

#include<stdio.h>

void mergesrt(int,int);

void merge(int,int,int);

int a[10];

void main()

          {

          int low,high,n,i;

          clrscr();

          printf("\nEnter array size:");

          scanf("%d",&n);

          printf("\nEnter the array:\n");

          for(i=0;i<n;i++)

                    {

                   scanf("%d",&a[i]);

                    }

          low=0;

          high=n-1;

          mergesrt(low,high);

          printf("\nSorted array:\n");

          for(i=0;i<n;i++)

                    {

                   printf("%d ",a[i]);

                    }

          getch();

          }

void mergesrt(int low,int high)

          {

          int mid;

          if(low!=high)

                    {

                   mid=(low+high)/2;

                   mergesrt(low,mid);

                   mergesrt(mid+1,high);

                   merge(low,mid,high);

                    }

          }

void merge(int low,int mid,int high)

          {      

          int temp[10];

          int i,j,k;

          i=low;

          j=mid+1;

          k=low;

          while((i<=mid)&&(j<=high))

                    {

                   if(a[i]<=a[j])

                             temp[k++]=a[i++];

                   else

                             temp[k++]=a[j++];

                    }

          while(i<=mid)

                   temp[k++]=a[i++];

          while(j<=high)

                   temp[k++]=a[j++];

          for(i=low;i<=high;i++)

                   a[i]=temp[i];

          }

Output

Enter array size:6

Enter the array:

12 7 -5 3 6 2

Sorted array:

-5 2 3 6 7 12