Merge Sort

Merge Sort- based On Divide and Conquer algorithm

 In Merge sort algorithm the given array is divided  into two parts and again merge with proper order.
1.Given array is divided into left and right half till we get two element in left half recursively.
2.After getting two element in left half call merge function it will first split array into single element namely left array and right array.
3.Then merge these two array using ascending order of left and right array.
4.Now move to right part of previous array,here also same procedure split array into left and right then merge.

Recursive Function:
Function call within same function is called recursive function.

Whenever function call occur within program the current value of the variables are push onto stack and pop again while returning the function call.
Hence here the index of array change according to function call and recursively left-right-merge is done.



Library files

#include<stdlib.h>
#include<stdio.h>
//Function Prototypes:
void merge(int arr[], int l, int m, int r,int arr_size);
void mergeSort(int arr[], int l, int r,int arr_size);
void printArray(int A[],int arr_size);
int y=0;//Counter for counting merge operation

int main()
{
    int arr[] = {35,25,48,4,8,72,13,100};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printf("Given array is \n");
    printArray(arr,arr_size);
    mergeSort(arr, 0, arr_size - 1,arr_size);
    printf("\nSorted array is \n");
    printArray(arr,arr_size);
    return 0;
}

// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r,int arr_size)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m,arr_size);// Recursive function call will execute till we get atleast two element in array
        mergeSort(arr, m+1, r,arr_size);// Recursive function call will execute till we get atleast two element in array

        merge(arr, l, m, r,arr_size);//this function will split array into two part and again merge with ascending order
    }
 }

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r,int arr_size)
{
y++;
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    //create temp arrays
    int L[n1], R[n2];
    //Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

    printf("\n array after %d times merge (merge function)\n",y);
    printArray(arr,arr_size);
}

void printArray(int A[], int arr_size)
{
    int i;
    for (i=0; i <= arr_size-1; i++)
    printf("\'%d\'\t ", A[i]);
    printf("\n");
}


/*
Output
Given array is
'35' '25' '48' '4' '8' '72' '13' '100'

 array after 1 times merge (merge function)
'25' '35' '48' '4' '8' '72' '13' '100'

 array after 2 times merge (merge function)
'25' '35' '4' '48' '8' '72' '13' '100'

 array after 3 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 4 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 5 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 6 times merge (merge function)
'4' '25' '35' '48' '8' '13' '72' '100'

 array after 7 times merge (merge function)
'4' '8' '13' '25' '35' '48' '72' '100'

Sorted array is
'4' '8' '13' '25' '35' '48' '72' '100'




*/