Q:

C Program to implement Merge Sort using Recursion

robaa
Save to bookmark
|
2022-11-25
|
  146 
0

Write a C Program to implement Merge Sort using Recursion. Here’s simple Program to implement Merge Sort using Recursion in C Programming Language.

C programming, examples, C programming examples,
login and add your own answer to this question

All Answers

robaa
2022-11-25
need an explanation for this answer? contact us directly to get an explanation for this answer

Recursion : :

  • Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.
  • The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
  • Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, etc.

Problem : :

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 implement Merge Sort using Recursion. The C Program is successfully compiled and run on a Windows system. The program output is also shown below.

SOURCE CODE : :

/*  C Program to implement Merge Sort 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("How Many elements u want to Sort :: ");
    scanf("%d", &size);

    printf("\nEnter [ %d ] elements below to be Sorted :: \n",size);

    for(i = 0; i < size; i++)
    {
        printf("\nEnter [ %d ] Element :: ",i+1);
         scanf("%d", &list[i]);
    }

    partition(list, 0, size - 1);

    printf("\n\nAfter implementing Merge sort, Sorted List is :: \n\n");
    for(i = 0;i < size; i++)
    {
         printf("%d   ",list[i]);
    }

    printf("\n");

   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];
    }
}

Output : :

/*  C Program to implement Merge Sort using Recursion  */

How Many elements u want to Sort :: 8

Enter [ 8 ] elements below to be Sorted ::

Enter [ 1 ] Element :: 4

Enter [ 2 ] Element :: 1

Enter [ 3 ] Element :: 3

Enter [ 4 ] Element :: 2

Enter [ 5 ] Element :: 5

Enter [ 6 ] Element :: 8

Enter [ 7 ] Element :: 6

Enter [ 8 ] Element :: 9


After implementing Merge sort, Sorted List is ::

1   2   3   4   5   6   8   9

Process returned 0

Above is the source code for C Program to implement Merge Sort using Recursion which is successfully compiled and run on Windows System.The Output of the program is shown above .

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C Sorting Solved Programs – C Programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Write a C Program to implement Quick Sort using re... >>
<< Write a C Program to Implement Selection Sort usin...