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