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* arr, int low, int mid, int high)
{
    int* temp = new int[high - low + 1];
    int i = low, j = mid + 1;
    int k = 0;
    while(i <= mid && j <= high)
    {
        if(arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while(i <= mid)
        temp[k++] = arr[i++];

    while(j <= high)
        temp[k++] = arr[j++];
    for(i = low, k = 0; i <= high; i++, k++)
        arr[i] = temp[k];
    delete[] temp;
}

void mergeSort(int* arr, int low, int high)
{
    if(low < high)
    {
        int mid = (low + high