合并排序不正确的排序（C ++）

我正在尝试实现合并排序，但是我的代码似乎缺少了一些东西。该代码似乎为最终结果错误地附加了每个子排序数组，并且在某些情况下，添加了元素的副本。

例如，如果我运行A=[1,3,5,2,4,6]该函数，我会得到A=[1,2,3,2,4,5,6]；似乎在1,2,3和之间夹了2个额外的字符4,5,6。另一个例子是A=[4,2,9,8,11,3]。当“排序”时，我得到A=[3,4,2,8,3,9,11]。为什么会这样呢？

vector<int> mergeSort(vector<int> A)
{
    if(A.size()<=1)
    {
        //print(A);
        return A;
    }
    vector<int> left;
    vector<int> right;
    for(unsigned int i=0; i < A.size()/2; i++)
        left.push_back(A[i]);
    for(unsigned int i=A.size()/2; i < A.size(); i++)
        right.push_back(A[i]);
    vector<int> sortedLeft = mergeSort(left);
    vector<int> sortedRight = mergeSort(right);
    vector<int>::iterator iterL=left.begin();
    vector<int>::iterator iterR;
    vector<int> output;
    while(iterL != left.end())
    {
        iterR=right.begin();
        while(iterR != right.end())
        {
            if(*iterR < *iterL)
            {
                //cout << "Pushing back " << *iterR << endl;
                output.push_back(*iterR);
            }
            iterR++;
        }
        //cout << "Pushing back " << *iterL << endl;
        output.push_back(*iterL);
        iterL++;
    }
    iterR=right.begin();
    while(iterR != right.end())//appends left-over elements in right to output
    {
        if(find(output.begin(), output.end(), *iterR) == output.end())
        {
            //cout << "Pushing back " << *iterR << endl;        
            output.push_back(*iterR);
        }
        iterR++;
    }
    return output;

下面是更新的while循环：

while(iterL != left.end())
    {
        iterR=right.begin();
        while(iterR != right.end() && *iterR != -1)
        {
            if(*iterR < *iterL)
            {
                //cout << "Pushing back " << *iterR << endl;
                output.push_back(*iterR);
                *iterR = -1;
            }
            iterR++;
        }
        //cout << "Pushing back " << *iterL << endl;
        output.push_back(*iterL);
        iterL++;
    }
    iterR=right.begin();
    while(iterR != right.end())//appends left-over elements in right to output
    {
        if(*iterR != -1)
        {
            output.push_back(*iterR);
        }
        iterR++;
    }