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.

#include <iostream>
using namespace std;

void merge(int *a, int n, int m) {
    int i, j, k;
    int *x = new int[n];
    for(i = 0, j = m, k = 0; k < n; k++) {
        x[k] = j == n      ? a[i++]
             : i == m      ? a[j++]
             : a[j] < a[i] ? a[j++]
             :               a[i++];
    }
    for(i = 0; i < n; i++) {
        a[i] = x[i];
    }
    delete[] x;
}
 
void merge_sort(int *a, int n) {
    if(n < 2)
        return;
    int m = n / 2;
    merge_sort(a, m);
    merge_sort(a + m, n - m);
    merge(a, n, m);
}
 
int main() {