Mohit Kumar Mohit Kumar - 2 months ago 9
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;
}

Answer

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.

Comments