The complexity of merge sort:
The time complexity of merge sort has been discussed in this link.
Code for merge sort:
#include<stdio.h>
void Merge(int a[], int left, int mid, int right, int n)
{
int leftSize = mid - left + 1, rightSize = right - mid;
int i, j, k, leftArray[leftSize], rightArray[rightSize];
for(i=0;i<leftSize;i++)
leftArray[i] = a[left+i];
for(i=0;i<rightSize;i++)
rightArray[i] = a[mid+1+i];
i = j = 0;
k = left;
while(i < leftSize && j < rightSize)
{
if(leftArray[i] < rightArray[j])
{
a[k++] = leftArray[i];
i++;
}
else
{
a[k++] = rightArray[j];
j++;
}
}
while(i < leftSize)
{
a[k++] = leftArray[i];
i++;
}
while(j < rightSize)
{
a[k++] = rightArray[j];
j++;
}
}
void MergeSort(int a[], int left, int right, int n)
{
int mid, i;
if(left < right)
{
mid = (left + right) / 2;
MergeSort(a, left, mid, n);
MergeSort(a, mid+1, right, n);
/*Uncomment the comment lines to see what is happening inside the merge sorting process*/
/*printf("Merging: ");
for(i=left;i<=mid;i++)
printf("%d ", a[i]);
printf("and ");
for(i=mid+1;i<=right;i++)
printf("%d ", a[i]);
printf("\n");*/
Merge(a, left, mid, right, n);
/*printf("After Merging:\n");
for(i=left;i<=right;i++)
printf("%d ", a[i]);
printf("\n");*/
}
}
int main()
{
int i, n, numbers[100];
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &numbers[i]);
MergeSort(numbers, 0, n-1, n);
printf("Sorted Output:\n");
for(i=0;i<n;i++)
printf("%d ", numbers[i]);
printf("\n");
return 0;
}
/*printf("Merging: ");
for(i=left;i<=mid;i++)
printf("%d ", a[i]);
printf("and ");
for(i=mid+1;i<=right;i++)
printf("%d ", a[i]);
printf("\n");*/
Merge(a, left, mid, right, n);
/*printf("After Merging:\n");
for(i=left;i<=right;i++)
printf("%d ", a[i]);
printf("\n");*/
}
}
int main()
{
int i, n, numbers[100];
scanf("%d", &n);
for(i=0;i<n;i++)
scanf("%d", &numbers[i]);
MergeSort(numbers, 0, n-1, n);
printf("Sorted Output:\n");
for(i=0;i<n;i++)
printf("%d ", numbers[i]);
printf("\n");
return 0;
}
/*
Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100
Sample Output:
Sorted Output:
12 33 44 55 66 77 88 99 100 555
*/
Tags:
C