MergeSort.cpp

#include<iostream>

using namespace std;

void makeArray(int* A, int n)
{
    for(int i = 0 ; i < n ; i++)
        cin>>A[i];
    return;
}

void printArray(int* A, int n)
{
    for(int i = 0 ; i < n ; i++)
        cout<<A[i]<<" ";
    return;
}

void Merge(int* A, int* LA, int* RA, int soA, int soL, int soR)
{
    int i = 0, j = 0, k = 0;
    
    while(i < soL && j < soR)
    {
        if(LA[i] < RA[j])
            A[k++] = LA[i++];
        else
            A[k++] = RA[j++];
    }
    
    while(i < soL)
        A[k++] = LA[i++];
    
    while (j < soR)
        A[k++] = RA[j++];
}

void MergeSort(int* A, int n)
{
    int mid;
    mid = n/2;
    
    //base case
    if(n < 2) return;
    
    int leftArr[mid];
    int rightArr[n-mid];
    
    for(int i = 0 ; i < mid ; i++)
        leftArr[i] = A[i];
    for(int i = mid ; i < n ; i++)
        rightArr[i-mid] = A[i];
    
    MergeSort(leftArr, mid);
    MergeSort(rightArr, n-mid);
    Merge(A,leftArr,rightArr,n,mid,n-mid);
}



int main()
{
    int n;
    cin>>n;
    
    int A[n];
    makeArray(A, n);
    
    MergeSort(A, n);
    
    printArray(A, n);
    
    
}