Merge Sort

Algorithm Video:

Merge Sort Combines Two Sorted file in a large bigger sorted files:
This Merge sort happens in a two steps:

This sorting is a example of divide and conquer approach:
1. Selection: Splits a list into two lists (This process is recursive approach)
2. Merging: It joins two list in a one list (It follows the pesudocode in itertive manner)

Pseudocode:

void Merges(int *A,int *left,int *right,int nR)
{
    nL=length of(L) //lenght of left
    nR=length of(R) //length of right
   
    i=0,j=0,k=0;

    while(i<nL && j<nR)
    {
        if(left[i]<=right[j])
        {
            A[k]=left[i];
            i=i+1;
        }
        else
        {
            A[k]=right[j];
            j=j+1;
        }
        k=k+1;
    }
    while(i<nL)
    {
        A[k]=left[i];
        k=k+1;
        i=i+1;
    }
    while(j<nR)
    {
        A[k]=right[j];
        j=j+1;
        k=k+1;
    }
}

void MergeSort(A)
{

    n=length of(A)
    if(n<2) return;
    int mid;

     mid=n/2;

    L=array of size(mid); //left
    R=array of size(n-mid); //right

    for(int i=0; i<mid; i++)
    {
        L[i]=A[i];
    }
    for(int i=mid; i<n; i++)
    {
        R[i-mid]=A[i];
    }

    MergeSort(L);
    MergeSort(R);
    Merges(A,L,R);
}

Implementation:
code with extra malloc declaration:

#include<bits/stdc++.h>
using namespace std;

void Merges(int *A,int *left,int nL,int *right,int nR)
{
    //int nL=sizeof(left)/sizeof(left[0]);
    //int nR=sizeof(right)/sizeof(right[0]);
    //cout<<nR<<" ";
    int i,j,k;
    i=0,j=0,k=0;

    while(i<nL && j<nR)
    {
        if(left[i]<=right[j])
        {
            A[k++]=left[i++];
            //i++;
        }
        else
        {
            A[k++]=right[j++];
          //  j++;
        }
        //k++;
    }
    while(i<nL)
    {
        A[k++]=left[i++];
        //k++;
        //i++;
    }
    while(j<nR)
    {
        A[k++]=right[j++];
        //j++;
        //k++;
    }
}

void MergeSort(int *A,int n)
{
    if(n<2) return;
    int mid,*L,*R;

     mid=n/2;


    L=(int*)malloc(mid*sizeof(int));
    R=(int*)malloc((n-mid)*sizeof(int));
    //int left[mid];
    //int right[n-mid];
   // int lefts=sizeof(left)/sizeof(left[0]);
    //cout<<lefts<<" size";
    for(int i=0; i<mid; i++)
    {
        L[i]=A[i];
    }
    for(int i=mid; i<n; i++)
    {
        R[i-mid]=A[i];
    }

    MergeSort(L,mid);
    MergeSort(R,n-mid);
    Merges(A,L,mid,R,n-mid);
    free(L);
    free(R);
}


int main()
{
    int A[]= {2,4,1,6,8,5,3,7};
    int sizes=sizeof(A)/sizeof(A[0]);
//Merges(A,0,8);
    MergeSort(A,sizes);
    for(int i=0; i<sizes; i++)
    {
        cout<<A[i]<<" ";
    }
    return 0;
}

code by me without  extra malloc:

#include<bits/stdc++.h>
using namespace std;

void Merges(int *A,int *left,int nL,int *right,int nR)
{
    //int nL=sizeof(left)/sizeof(left[0]); //i am not using this explained in this link

    //int nR=sizeof(right)/sizeof(right[0]); //https://www.youtube.com/watch?v=CpjVucvAc3g
    
    int i,j,k;
    i=0,j=0,k=0;

    while(i<nL && j<nR)
    {
        if(left[i]<=right[j])
        {
            A[k++]=left[i++];
        }
        else
        {
            A[k++]=right[j++];
          
        }
        
    }
    while(i<nL)
    {
        A[k++]=left[i++];
    }
    while(j<nR)
    {
        A[k++]=right[j++];
    }
}

void MergeSort(int *A,int n)
{
    if(n<2) return;
    int mid;

     mid=n/2;

    int L[mid];
    int R[n-mid];

    for(int i=0; i<mid; i++)
    {
        L[i]=A[i];
    }
    for(int i=mid; i<n; i++)
    {
        R[i-mid]=A[i];
    }

    MergeSort(L,mid);
    MergeSort(R,n-mid);
    Merges(A,L,mid,R,n-mid);
}


int main()
{
    int A[]= {2,4,1,6,8,5,3,7};
    int sizes=sizeof(A)/sizeof(A[0]);
//Merges(A,0,8);
    MergeSort(A,sizes);
    for(int i=0; i<sizes; i++)
    {
        cout<<A[i]<<" ";
    }
    return 0;
}

output:

1 2 3 4 5 6 7 8

Analysis of Running Time Complexity:

Worst case, Best case, Avergae case: Theta(nlogn)
Space Complexity: Theta(n)

This link can help to solve problems:
https://gist.github.com/mycodeschool/9678029
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/

http://www.sanfoundry.com/cpp-program-implement-merge-sort/