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.

// C++ program to implement Merge Sort algorithm 
#include <bits/stdc++.h> 
using namespace std; 
  
// A function to merge the two half into a sorted data. 
void Merge(int *a, int low, int high, int mid) 
{ 
    // We have low to mid and mid+1 to high already sorted. 
    int i, j, k, temp[high-low+1]; 
    i = low; 
    k = 0; 
    j = mid + 1; 
  
    // Merge the two parts into temp[]. 
    while (i <= mid && j <= high) 
    { 
        if (a[i] < a[j]) 
        { 
            temp[k] = a[i]; 
            k++; 
            i++; 
        } 
        else 
        { 
            temp[k] = a[j]; 
            k++; 
            j++; 
        } 
    } 
  
    // Insert all the remaining