Program
Time Complexity: O(n log n)
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
void Merge(int a[], int low, int mid, int high)
{
int i, j, k, b[20];
i = low;
j = mid + 1;
k = low;
while (i <= mid && j <= high)
{
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i <= mid)
b[k++] = a[i++];
while (j <= high)
b[k++] = a[j++];
for (k = low; k <= high; k++)
a[k] = b[k];
}
void MergeSort(int a[], int low, int high)
{
int mid;
if (low >= high)
return;
mid = (low + high) / 2;
MergeSort(a, low, mid);
MergeSort(a, mid + 1, high);
Merge(a, low, mid, high);
}
void main()
{
int n, a[2000], i;
clock_t st, et;
double ts;
printf("*********************************************************");
printf("\n*********************************************************");
printf("\n** WAP for merge sort with time complexity in C **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n*********************************************************");
printf("\n*********************************************************");
printf("\n Enter How many Numbers:");
scanf("%d", &n);
printf("\nEnter array elements\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
st = clock();
MergeSort(a, 0, n - 1);
et = clock();
ts = (double)(et - st) / CLOCKS_PER_SEC;
printf("\n Sorted Numbers are : \n");
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
printf("\nThe time taken is %e", ts);
}
Output 1
********************************************************* ********************************************************* ** WAP for merge sort with time complexity in C ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** ********************************************************* ********************************************************* Enter How many Numbers:8 Enter array elements 12 21 12 23 32 31 14 41 Sorted Numbers are : 12 12 14 21 23 31 32 41 The time taken is 0.000000e+000