Write a C ++ program to implement Merge Sort algorithm to efficiently handle an input array that may contain duplicate elements. The goal is to modify the algorithm in such a way that duplicate elements appear in the sorted array in the same order as they appear in the input.

int a[100], n;
int main()
{
    int i, j, k, mid, temp;
    cout<<"enter the number of elements\n";
    cin>>n;
    cout<<"enter the elements\n";
    for(i=0; i<n; i++)
    {
        cin>>a[i];
    }
    merge_sort(0, n-1);
    cout<<"sorted array\n";
    for(i=0; i<n; i++)
    {
        cout<<a[i]<<"\t";
    }
    return 0;
}
void merge_sort(int low, int high)
{
    int mid;
    if(low<high)
    {
        mid=(low+high)/2;
        merge_sort(low, mid);
        merge_sort(mid+1, high);
        merge(low, mid, high);
    }
}
void merge(int low, int mid, int high)
{
    int h, i,