Search Tutorials

Saturday 20 April 2013

C code to implement Merge Sort

//C program to implement Merge Sort//

#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>

#define MAXARRAY 10

void mergesort(int a[], int low, int high);

void main(void)
{
int array[MAXARRAY];
int i = 0;
    clrscr();
    randomize();
 /* load some random values into the array */
for(i = 0; i < MAXARRAY; i++)
{
array[i] = rand() % 100; 
}

 /* array before mergesort */
printf("Before    :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}

     printf("\n");

mergesort(array, 0, MAXARRAY - 1);

 /* array after mergesort */
printf("Mergesort :");
for(i = 0; i < MAXARRAY; i++)
{
printf(" %d", array[i]);
}

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

void mergesort(int a[], int low, int high)
{
int i = 0;
int length = high - low + 1;
int pivot  = 0;
int merge1 = 0;
int merge2 = 0;
int *working;
    working=(int*)malloc(length*2);
if(low == high)
{
return;
}
pivot  = (low + high) / 2;

mergesort(a, low, pivot);
mergesort(a, pivot + 1, high);
 
for(i = 0; i < length; i++)
     {
working[i] = a[low + i];
}

merge1 = 0;
merge2 = pivot - low + 1;

for(i = 0; i < length; i++) {
{
if(merge2 <= high - low)
if(merge1 <= pivot - low)
if(working[merge1] > working[merge2])
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
else
a[i + low] = working[merge2++];
else
a[i + low] = working[merge1++];
}
}
}

No comments:

Post a Comment

Back to Top