mergesort
#include <stdio.h>
void merge(int a[], int low, int high, int mid, int *c)
{
int i, j, k, b[10];
i = low;
j = mid + 1;
k = low;
while (i <= mid && j <= high)
{
(*c)++;
if (a[i] < a[j])
{
b[k] = a[i];
i++;
}
else
{
b[k] = a[j];
j++;
}
k++;
}
while (i <= mid)
{
b[k] = a[i];
i++;
k++;
}
while (j <= high)
{
b[k] = a[j];
j++;
k++;
}
for (k = low; k <= high; k++)
{
a[k] = b[k];
}
}
void mergesort(int a[], int low, int high, int *c)
{
if (low < high)
{
int mid = (low + high) / 2;
mergesort(a, low, mid, c);
mergesort(a, mid + 1, high, c);
merge(a, low, high, mid, c);
}
}
int main()
{
int size;
printf("Enter the size of array: ");
scanf("%d", &size);
int a[size];
int c = 0;
int low = 0;
int high = size - 1;
printf("Enter the elements of array: ");
for (int i = 0; i < size; i++)
{
scanf("%d", &a[i]);
}
mergesort(a, low, high, &c);
printf("Array after sorting is: ");
for (int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
printf("Number of comparisons required: %d\n", c);
return 0;
}
Comments
Post a Comment