The line close to the end of Marge
k1 = q - i+1 ;
should be
k1 += n1 - i;
Firstly you are keeping a running total of how many elements of L
an element of R
has to be moved in front of. Therefore the operator should be +=
not =
.
Secondly q
measures a position in the original array A
. You are counting a number of elements in the small array L
, and so you should be subtracting the index from n1
, the size of that array (not including the guard value). If A
were huge, you would start to see crazy results: when you were merging small sub-arrays with only a few elements, but very close to the top of A
, you would see huge values for q
, which have nothing to do with the size of L
.
When you've made sure your code is working, you should head over to codereview.stackexchange.com. They only help with working code, but they will give you lots of pointers about how to write things in a cleaner and more readable way. Your code is full of small errors like unnecessary namespaces, unused initializations and so on (but I think it is the correct approach to get it working right before worrying about these).