合併排序

Question

大家好我目前正致力於實現合併排序算法，我已經讓我的代碼能夠工作，但是我的工作仍然存在問題。例如，當我輸入「1 3 5 2」時，我收到「1 3 5 5」。我希望找到一些幫助來確定我的錯誤，因爲即使使用cerr語句，我也無法這樣做。謝謝

vector<int> VectorOps::mergeSort(vector<int> toSort) 
{ 
if (toSort.size() <= 1) 
{ 
return toSort; 

} 

std::vector<int>::iterator middle = toSort.begin() + (toSort.size()/2); 

vector<int> left(toSort.begin(), middle); 
vector<int> right(middle, toSort.end()); 
left = mergeSort(left); 
right = mergeSort(right); 
cerr << "The numbers are "<< endl; 
return merge(left, right); 

} 


vector<int> merge(const vector<int>& left, const vector<int>& right) 
{ 

    vector<int> toReturn; 
    unsigned left_it = 0, right_it = 0; 

    while(left_it < left.size() && right_it < right.size()) 
    { 



    if(left[left_it] < right[right_it]) 
    { 
    toReturn.push_back(left[left_it]); 
    left_it++; 


    } 
    else 
    { 

     toReturn.push_back(left[left_it]); 
     right_it++; 
    } 
    } 
    while(left_it < left.size()) 
    { 
     toReturn.push_back(left[left_it]); 
     left_it++; 
    } 

    while(right_it < right.size()) 
    { 
     toReturn.push_back(right[right_it]); 
     right_it++; 

    } 




return toReturn; 

} 

Answer 1

在第一個條件的merge，兩個分支有

toReturn.push_back(left[left_it]); 

其中之一應該是

toReturn.push_back(right[right_it]); 

這就是爲什麼複製和粘貼被認爲是有害的。

Answer 2

變化toReturn.push_back(left[left_it]);到toReturn.push_back(left[right_it]);