algorithm - 了解归并排序算法

Question

我正在研究合并排序算法，并尝试使用这段算法递归地理解它的方法:

MergeSort(A, p, r)
If p > r 
    return;
q = (p+r)/2;
mergeSort(A, p, q) 
mergeSort(A, q+1, r)
merge(A, p, q, r)

我尝试对大小为 3 的数组进行演练。

[0,1,2]
mergesort(A,0,2)----[0,1,2]
mergesort(A,0,1)----[0,1]
mergesort(A,0,0)----[0]
mergesort(A,1,2)----[1,2]
mergesort(A,2,2)----[2]
merge(A,0,1,2)

虽然我能够理解其基本的分而治之技术，但我无法正常试运行。我知道我遗漏了一些东西。任何人都可以帮助我或指出遗漏的部分。

请注意，我只关心如何试运行这个算法。

Answer 1

if 需要修复:

MergeSort(A, p, r)
If p >= r 
    return;
q = (p+r)/2;
mergeSort(A, p, q) 
mergeSort(A, q+1, r)
merge(A, p, q, r)

示例试运行，递归级别缩进

[0,1,2]
mergesort(A,0,2)--------[0,1,2]
  mergesort(A,0,1)------[0,1]
    mergesort(A,0,0)----[0]
    mergesort(A,1,1)----[1]
    merge(A,0,0,1)------[0]+[1]
  mergesort(A,2,2)------[2]
  merge(A,0,1,2)--------[0,1]+[2]

将变量更改为 b(开始)、e(结束 = 最后 + 1)、m(中间)

MergeSort(A, b, e)
If (e - b) < 2
    return;
m = (b+e)/2;
mergeSort(A, b, m) 
mergeSort(A, m, e)
merge(A, b, m, e)

试运行示例

[0,1,2]
mergesort(A,0,3)--------[0,1,2]
  mergesort(A,0,1)------[0]
  mergesort(A,1,3)------[1,2]
    mergesort(A,1,2)----[1]
    mergesort(A,2,3)----[2]
    merge(A,1,2,3)------[1]+[2]
  merge(A,0,1,3)--------[0]+[1,2]

另一个试运行示例

[0,1,2,3]
mergesort(A,0,4)--------[0,1,2,3]
  mergesort(A,0,2)------[0,1]
    mergesort(A,0,1)----[0]
    mergesort(A,1,2)----[1]
    merge(A,0,1,2)------[0]+[1]
  mergesort(A,2,4)------[2,3]
    mergesort(A,2,3)----[2]
    mergesort(A,3,4)----[3]
    merge(A,2,3,4)------[2]+[3]
  merge(A,0,2,4)--------[0,1]+[2,3]