Mega Code Archive
Msort, merge sort [array]
<![CDATA[
#include <stdio.h>
#include <stdlib.h>
#define MAXARRAY 10
void mergesort(int a[], int low, int high);
int main(void) {
int array[MAXARRAY];
int i = 0;
/* 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");
return 0;
}
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[length];
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++];
}
}
]]>