C Program to Input Few Numbers & Perform Merge Sort on them using Recursion

«
»
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.

  1. /*
  2.  * C Program to Input Few Numbers & Perform Merge Sort on them using Recursion
  3.  */
  4.  
  5. #include <stdio.h>
  6.  
  7. void mergeSort(int [], int, int, int);
  8. void partition(int [],int, int);
  9.  
  10. int main()
  11. {
  12.     int list[50];
  13.     int i, size;
  14.  
  15.     printf("Enter total number of elements:");
  16.     scanf("%d", &size);
  17.     printf("Enter the elements:\n");
  18.     for(i = 0; i < size; i++)
  19.     {
  20.          scanf("%d", &list[i]);
  21.     }
  22.     partition(list, 0, size - 1);
  23.     printf("After merge sort:\n");
  24.     for(i = 0;i < size; i++)
  25.     {
  26.          printf("%d   ",list[i]);
  27.     }
  28.  
  29.    return 0;
  30. }
  31.  
  32. void partition(int list[],int low,int high)
  33. {
  34.     int mid;
  35.  
  36.     if(low < high)
  37.     {
  38.         mid = (low + high) / 2;
  39.         partition(list, low, mid);
  40.         partition(list, mid + 1, high);
  41.         mergeSort(list, low, mid, high);
  42.     }
  43. }
  44.  
  45. void mergeSort(int list[],int low,int mid,int high)
  46. {
  47.     int i, mi, k, lo, temp[50];
  48.  
  49.     lo = low;
  50.     i = low;
  51.     mi = mid + 1;
  52.     while ((lo <= mid) && (mi <= high))
  53.     {
  54.         if (list[lo] <= list[mi])
  55.         {
  56.             temp[i] = list[lo];
  57.             lo++;
  58.         }
  59.         else
  60.         {
  61.             temp[i] = list[mi];
  62.             mi++;
  63.         }
  64.         i++;
  65.     }
  66.     if (lo > mid)
  67.     {
  68.         for (k = mi; k <= high; k++)
  69.         {
  70.             temp[i] = list[k];
  71.             i++;
  72.         }
  73.     }
  74.     else
  75.     {
  76.         for (k = lo; k <= mid; k++)
  77.         {
  78.              temp[i] = list[k];
  79.              i++;
  80.         }
  81.     }
  82.  
  83.     for (k = low; k <= high; k++)
  84.     {
  85.         list[k] = temp[k];
  86.     }
  87. }

advertisement
$ 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

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at other example programs on Searching and Sorting, go to C Programming Examples on Searching and Sorting. If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.