Sample C Program To Implement Merge Sort Using Divide & Conquer Strategy.

ALGORITHM:

STEP 1: Start the program.
STEP 2: Read the value of n.
STEP 3: Set a for loop to read the elements of array.
for (i = 0; i < n; i++)
STEP 4: Call the function split ( a, 0, n – 1 )
STEP 5: Print the sorted array a.
STEP 6: Stop the program.


FUNCTION MERGE_SORT (int *a, int low, int high)

STEP 1: Declare the local variable.
STEP 2: If low is less than high then assign the mean value of low and high to mid.
mid = ( low + high ) / 2
STEP 3: Call the function merge_sort ( a, low, mid ).
STEP 4: Call the another function merge_sort ( a, mid + 1, high ).
STEP 5: Call the function combine ( a, low, mid, high ).


FUNCTION SPLIT(int *c, int first, int last)

STEP 1: Declare the local variables.
STEP 2: Set the while loop till the condition i <= mid && j <= high is failed.
STEP 3: Check whether a[i] < a[j]
STEP 4: If so the assign the value of a[j] to temp[k] and increment j and k
temp[k] = a[i]
j++
k++
STEP 5: Else assign a[j] to temp[k] and then increment j and k
temp[k]=a[j]
j++
k++

STEP 6: Set another while loop till i is less than mid.
STEP 7: Assign the value of a[i] to temp[k]
temp[k] = a[i]
j++
k++
STEP 8: Set another while loop till j is greater than mid.
STEP 9: Assign the value of a[j] to temp[k]
temp[k] = a[j]
j++
k++
STEP 10: Construct a for loop for k.
for(k = low; k <= high; k++)

STEP 11: Assign the value of temp[k] to a[k].
a[k] = temp[k]


SAMPLE PROGRAM:

#include<stdio.h>
#include<conio.h>

void split(int *, int, int);
void merge(int *, int, int, int, int);
int a[25], b[25];

void main()
{

int i, n;
clrscr();
printf(" Enter the limit ");
scanf(" %d ", &n);

printf(" \n Enter the elements ");

for(i = 0; i < n; i++)
scanf(" %d ", &a[i]);

split(a, 0, n – 1 );
printf("\n The sorted list is: ");

for(i = 0 ;i < n; i++)
printf(" \n %d ", a[i]);

getch();

}


void split(int *c, int first, int last)
{

int mid;
if(first < last)
{
mid = ( first + last ) / 2;

split(c, first, mid);
split(c, mid+1, last);

merge(c, first, mid, mid + 1, last);

}
}


void merge(int *a, int f1, int l1, int f2, intl2)
{

int i, j, k = 0;
i = f1;
j = f2;
while(i <= l1&& j <= l2)
{

if(a[i] < a[j])
b[k] = a[i++];
else
b[k] = a[j++];

k++;
}

while(i <= l1)
b[k++] = a[i++];

while(j <= l2)
i = f1;

j = 0;

while(i <= l2 && j < k)
a[i++] = b[j++]

}



OUTPUT:

Enter the limit: 6
Enter the elements
23
45
89
98
09
65
The Sorted List is: 09 23 45 65 89 98




NOTE:

If you liked the post/article or if you think this post/article helped you in any way, then please show your appreciation by filling up at least one form from the options given below: