C Program to Input Few Numbers & Perform Merge Sort on them using Recursion
Posted by Superadmin on December 09 2015 04:29:04
The following C program, using recursion, performs merge sort. A merge sort is a sorting algorithm with complexity of O(nlogn). It is used for sorting numbers, structure, files.
The following C program, using recursion, performs merge sort. A merge sort is a sorting algorithm with complexity of O(nlogn). It is used for sorting numbers, structure, files.
Here is the source code of the C program to display a linked list in reverse. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C Program to Input Few Numbers & Perform Merge Sort on them using Recursion
*/
#include <stdio.h>
void mergeSort(int [], int, int, int);
void partition(int [],int, int);
int main()
{
int list[50];
int i, size;
printf("Enter total number of elements:");
scanf("%d", &size);
printf("Enter the elements:\n");
for(i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
partition(list, 0, size - 1);
printf("After merge sort:\n");
for(i = 0;i < size; i++)
{
printf("%d ",list[i]);
}
return 0;
}
void partition(int list[],int low,int high)
{
int mid;
if(low < high)
{
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}
}
void mergeSort(int list[],int low,int mid,int high)
{
int i, mi, k, lo, temp[50];
lo = low;
i = low;
mi = mid + 1;
while ((lo <= mid) && (mi <= high))
{
if (list[lo] <= list[mi])
{
temp[i] = list[lo];
lo++;
}
else
{
temp[i] = list[mi];
mi++;
}
i++;
}
if (lo > mid)
{
for (k = mi; k <= high; k++)
{
temp[i] = list[k];
i++;
}
}
else
{
for (k = lo; k <= mid; k++)
{
temp[i] = list[k];
i++;
}
}
for (k = low; k <= high; k++)
{
list[k] = temp[k];
}
}
$ cc pgm28.c
$ a.out
Enter total number of elements:5
Enter the elements:
12
36
22
76
54
After merge sort:
12 22 36 54 76