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>
#include <vector>
#include <algorithm>

using namespace std;

void merge_sort(int *, int, int);
void merge(int *, int, int, int);
void print(int *, int);

void merge_sort(int *arr, int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2;
        merge_sort(arr, l, m);
        merge_sort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

void merge(int *arr, int l, int m, int r) {
    vector<int> L;
    vector<int> R;
    int i, j, k;

    for (i = l; i <= m; i++) {
        L.push_back(arr[i]);
    }

    for (i = m+1; i <= r; i++) {
        R.push_back(arr[i]);