計數反演使用歸併

Question

我試圖實現使用歸併在MATLAB反轉計數器，但由於某些原因，一些問題的答案是路要走。例如，[3,4,8,1]中的反轉次數是3，但是我得到了2.但是，數組被正確排序，所以我認爲我計算分裂反轉的方式是問題。

這裏是我的代碼：

function [count, sorted] = mergesort(A) 
% count is the number of inversions; sorted is the sorted array. 

n = length(A); 
if n == 1 
    count = 0; 
    sorted = A; 
else 
    m = ceil(n/2); 
    [count1, sorted1] = mergesort(A(1:m)); 
    [count2, sorted2] = mergesort(A(m+1:n)); 
    [crosscount, sorted] = merge(sorted1, sorted2); 
    count = count1 + count2 + crosscount; 
end 
end 

function [crosscount, z] = merge(x, y) 

n = length(x); m = length(y); z = zeros(1, n+m); 
ix = 1; 
iy = 1; 
crosscount = 0; 
for iz = 1:(n+m); 
    if ix > n 
     z(iz) = y(iy); 
     iy = iy + 1; 
    elseif iy > m 
     z(iz) = x(ix); 
     ix = ix + 1; 
     crosscount = crosscount + (n + 1 - ix); %this might be wrong 
    elseif x(ix) <= y(iy) 
     z(iz) = x(ix); 
     ix = ix + 1; 
    elseif x(ix) > y(iy) 
     z(iz) = y(iy); 
     iy = iy + 1; 
     crosscount = crosscount + 1; %im pretty sure this is right 
    end 
end 
end 

Answer 1

好了，所以朋友幫我找到答案。我的直覺是正確的，但我需要一位實際程序員的幫助，以瞭解我出錯的地方：

elseif iy > m 
     z(iz) = x(ix); 
     ix = ix + 1; 
     crosscount = crosscount + (n + 1 - ix); **%this might be wrong - this is actually wrong, since you don't want to count if you're traversing beyond the edge of the right array, and since the actual counting is happening in the last if case** 
    elseif x(ix) <= y(iy) 
     z(iz) = x(ix); 
     ix = ix + 1; 
    elseif x(ix) > y(iy) 
     z(iz) = y(iy); 
     iy = iy + 1; 
     crosscount = crosscount + **(n + 1 - ix)** **this is right because you're counting the remaining numbers in your left array that are also greater than y(iy) and just adding that to your count** 
    end