Mohit Kumar - 1 year ago 70
C++ Question

# Merge Sorting fails to merge parts at the end of process

I tried sorting with the simple case of

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

It does the spliting and merging of subparts in lefthalf and righthalf as

``````{11 12} & {5 6 13}
``````

which is desired. But during Final Merging it takes lefthalf and righthalf as

``````{12 11} & {13 5 6}
``````

And this gives the wrong answer of :

``````{12 11 13 5 6}
``````

Why is this Happening ? Here is my code.

``````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;
}
``````

The problem here is subtle and not easily noticed by new developers. You're passing your argument to `mergsrt` by value, which means a copy is made. The sorting is done on this copy, and the original deque is not changed. You need to pass by reference (`mergsrt(deque<int> &)`) instead.