C Programming Code Examples

C > Recursion Code Examples

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



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.

    #include <stdio.h>

    void mergeSort(int [], int, int, int);

    void partition(int [],int, int);

    int main()

    {

        int list[50];

        int j, size;

        printf("Enter total number of elements:");

        scanf("%d", &size);

        printf("Enter the elements:\n");

        for(j = 0; j < size; j++)

        {

             scanf("%d", &list[j]);

        }

        partition(list, 0, size - 1);

        printf("After merge sort:\n");

        for(j = 0;j < size; j++)

        {

             printf("%d   ",list[j]);

        }

       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 j, mi, k, lo, temp[50];

        lo = low;

        j = low;

        mi = mid + 1;

        while ((lo <= mid) && (mi <= high))

        {

            if (list[lo] <= list[mi])

            {

                temp[j] = list[lo];

                lo++;

            }

            else

            {

                temp[j] = list[mi];

                mi++;

            }

            j++;

        }

        if (lo > mid)

        {

            for (k = mi; k <= high; k++)

            {

                temp[j] = list[k];

                j++;

            }

        }

        else

        {

            for (k = lo; k <= mid; k++)

            {

                 temp[j] = list[k];

                 j++;

            }

        }

        for (k = low; k <= high; k++)

        {

            list[k] = temp[k];

        }

    }