小编Sim*_*men的帖子

我不太清楚为什么我的merge-sort实现不起作用.

merge_sort将数组A作为参数,以及起始和最终索引p和r.如果我尝试在A = [1,64,64,315,14,2,3,4,5]上运行merge_sort(A,1,9),A将变为A = [1,1,1,1, 1,2,2,4,5].我正在尝试使用标记来检测L和R阵列是否已经耗尽.

这是代码:

function merge_sort(A, p, r)
    if p < r
        q = floor(Int, (p+r)/2)
        merge_sort(A, p, q)
        merge_sort(A, q+1, r)
        merge(A, p, q, r)
    end
end



function merge(A, p, q, r)
    n1 = q-p+1
    n2 = r-q
    L = []
    R = []

    for i = 1:n1
      push!(L, A[p+1-1])
    end

    for j = 1:n2
      push!(R, A[q+j])
    end

    sentinel = 123456789
    push!(L, sentinel)
    push!(R, sentinel)
    i=1
    j=1

    for k=p:r
      if L[i] <= R[j]
         A[k] = …