IndianTechnoEra: Merge Sorting technique using Divide and Conquer approach

 What is Merge sort?

Merge sort is one of the most efficient sorting algorithms. It is based on the divide-and-conquer strategy. Merge sort continuously cuts down a list into multiple sublists until each has only one item, then merges those sublists into a sorted list.

An example of merge sort. First, divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged.

What is the divide and conquer approach?

A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

User Input: Random Generated elements input in array

Code:

// Merge sort in C

#include <stdio.h>

// Merge two subarrays L and M into arr

void merge(int arr[], int p, int q, int r)

{

    // Create L ? A[p..q] and M ? A[q+1..r]

    int n1 = q - p + 1;

    int n2 = r - q;

    int L[n1], M[n2];

    for (int i = 0; i < n1; i++)

        L[i] = arr[p + i];

    for (int j = 0; j < n2; j++)

        M[j] = arr[q + 1 + j];

    // Maintain current index of sub-arrays and main array

    int i, j, k;

    i = 0;

    j = 0;

    k = p;

    // Until we reach either end of either L or M, pick larger among

    // elements L and M and place them in the correct position at A[p..r]

    while (i < n1 && j < n2)

    {

        if (L[i] <= M[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = M[j];

            j++;

        }

        k++;

    }

    // When we run out of elements in either L or M,

    // pick up the remaining elements and put in A[p..r]

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

    while (j < n2)

    {

        arr[k] = M[j];

        j++;

        k++;

    }

}

// Divide the array into two subarrays, sort them and merge them

void mergeSort(int arr[], int l, int r)

{

    if (l < r)

    {

        // m is the point where the array is divided into two subarrays

        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);

        mergeSort(arr, m + 1, r);

        // Merge the sorted subarrays

        merge(arr, l, m, r);

    }

}

// Print the array

void printArray(int arr[], int size)

{

    for (int i = 0; i < size; i++)

        printf("%d\t ", arr[i]);

    printf("\n");

}

// Driver program

int main()

{

    int i, j, n;

   

    printf("\nAim: Merge Sorting technique using Divide and Conquer approach in C");

    printf("\nUser Input: By user");

    printf("\n==============================================\n");

    // taking input the size of array

    printf("\nEnter the size of the array : ");

    scanf("%d", &n);

    int arra[n];

    // Generating an array of given size

    for (i = 0; i < n; i++)

    {

        arra[i] = rand() % 100;

    }

    // Printing the autogenerated array

    printf("\nAuto generated %d elements list of the array: \n", n);

    for (i = 0; i < n; i++)

    {

        printf("A[%d]\t %d\n ",i+1, arra[i]);

    }

    int size = sizeof(arra) / sizeof(arra[0]);

    mergeSort(arra, 0, size - 1);

    printf("\n\nThe Sorted elements list of the array by Merge Sorting technique using Divide and Conquer approach:\n");

    printArray(arra, size);

}

Output: