Code:
int main(int argc, char **argv)
{
int array[100];
int item,j, i=0;
int *comp = malloc(sizeof(int));
int comp_result;
clock_t start, stop;
double t;
while(scanf("%d", &item) > 0)
{
array[i] = item;
i++;
}
start = clock();
sort(array,i,comp);
stop = clock();
t = (double)(stop-start)/(double)(CLOCKS_PER_SEC);
comp_result = *comp;
for(j=0; j < i; j++)
printf("%d ", array[j]);
printf("\n");
printf("%d comparisons made\n", comp_result);
printf("Time taken : %.10g\n", t);
return 0;
}
void sort(int array[],int size, int *comp)
{
int b[100];
int n=size;
naturalmergesort(array, b, n, comp);
}
static bool mergeruns(int a[], int b[], int n, int *comp)
{
int i=0, k=0, x;
bool asc=true;
while (i<n)
{
k=i;
do x=a[i++]; while (i<n && x<=a[i]);
while (i<n && x>=a[i]) x=a[i++];
merge (a, b, k, i-1, asc, comp);
asc=!asc;
}
return k==0;
}
void merge(int a[], int b[], int lo, int hi, bool asc, int *comp)
{
int l = lo; int r = hi;
int k=asc ? l : r;
int c=asc ? 1 : -1;
int i=lo, j=hi;
int comparisons = 0;
while (i<=j)
{
if (a[i]<=a[j])
{
b[k]=a[i++];
comparisons++;
}
else
{
b[k]=a[j--];
comparisons++;
}
k+=c;
}
*comp = comparisons;
/*printf("%d comparisons made\n", comparisons);*/
}
void naturalmergesort(int a[], int b[], int n, int *comp)
{
while (!mergeruns(a, b, n, comp) & !mergeruns(b, a, n, comp));
}
There's another one for sorting structs, but it's rather lengthy...