你如何为我的 mergeSort 递归制作这个伪代码合并函数算法

Question

merge(A[p..r],q)
k<-0
i<-p
j<-q+1
while(i<=q && j<=r){
    if A[i]<= A[j]
        B[++k]<-A[i++]
    else
        B[++k]<-A[j++]
}
for m <-i to q
    B[++k]<-A[m]
for n <- j to r
B[++k]<-A[n]
i<-p
for e <- i to k
    A[i++]<-B[e]

我知道递归函数必须调用自己来执行算法。 但是我无法对它的概念进行思考，你能帮我开始递归地写它吗？

Answer 1

假设你有一个功能正常的merge()函数，你需要思考

如何将问题拆分为较小的问题，然后使用我的 merge()功能组合答案

这个想法是将数组分成两半，递归地调用每半的mergeSort()。假设递归算法工作正常，所以当你从递归返回时 - 现在每一半都被排序了。
因此，您基本上有 2 个排序数组，您需要使用 merge() 函数将它们合并为一个数组。

伪代码应如下所示：

mergeSort(arr, start, end):
   if (end-start) <= 1: //array of size 1 is already sorted
        return
   mid = (end-start)/2 + start
   mergeSort(arr,start,mid)
   mergeSort(arr,mid+1,end)
   //here, you assume that mergeSort works, 
   //thus each half of the array is sorted on its own
   merge(arr,start,end,mid)