Merge Сортировка не удается объединить части в конце процесса

Question

Я попытался сортировки с простого случая

test = {12, 11, 13, 5, 6}; 

Это делает spliting и слияние подразделов в lefthalf и righthalf как

{11 12} & {5 6 13} 

который хочет. Но в Final Слияния он принимает lefthalf и righthalf, как

{12 11} & {13 5 6} 

И это дает неправильный ответ:

{12 11 13 5 6} 

Почему это происходит? Вот мой код.

void mergesrt(deque<int> mydeq){ 
if (mydeq.size() > 1){ 
    int mid = mydeq.size()/2; 
    deque<int> lefthalf(mydeq.begin(), mydeq.begin() + mid); 
    deque<int> righthalf(mydeq.begin() + mid, mydeq.begin() + mydeq.size()); 
    mergesrt(lefthalf); 
    mergesrt(righthalf); 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    cout << "--------------merging-----------" << endl; 

    while (i < lefthalf.size() && j < righthalf.size()){ 
    if (lefthalf[i] < righthalf[j]){ 
      mydeq[k] = lefthalf[i]; 
      k++; 
      i++; 
    } 
    else{ 
      mydeq[k] = righthalf[j]; 
      k++; 
      j++; 
      } 
      } 

    while (i < lefthalf.size()){ 
      mydeq[k] = lefthalf[i]; 
      k++; 
      i++; 
      } 

    while (j < lefthalf.size()){ 
      mydeq[k] = righthalf[j]; 
      k++; 
      j++; 
      } 
      } 

     return; 
     } 

Answer 1

Проблема здесь тонкая и не легко замечаемая новыми разработчиками. Вы передаете свой аргумент mergsrt по значению, что означает, что копия сделана. Сортировка выполняется на этой копии, и исходный deque не изменяется. Вы должны пройти по ссылке (mergsrt(deque<int> &)).