Подсчет инверсий в MATLAB с использованием MergeSort

Question

Я пытаюсь реализовать счетчик инверсии в MATLAB с помощью MergeSort, но по некоторым причинам некоторые из ответов удалены. Например, количество инверсий в [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