归并排序算法的调用机制

Question

调用第一个合并排序函数，直到满足 if 条件现在据我所知，如果不满足 if-conditon 那么它的主体将不会执行

在不满足 if-conditon 2nd mergesort 函数后我无法理解called.so这是怎么回事？请详细说明

mergesort (int*a,int*b,int low,int high)

{

     int  pivot
     if(low<high)
      {
               pivot=(low+high)/2;
               mergesort(a,b,low,pivot);/*1st*/
               mergesort(a,b,pivot+1,high);/*2nd*/
               merge(a,b,low,pivot,high);
       }
     return ;
}

Answer 1

my question is why mergesort(a,b,pivot+1,high) is called?

mergesort(a,b,pivot+1,high)被调用是因为之前的语句mergesort(a,b,low,pivot)只对数组的下半部分进行排序，数组的上半部分还需要排序为了使 merge(a, b, low, pivot, high) 有效（如果数组的部分未排序，则 .

例如。

假设您有一个大小为 5 的数组 {e, d, c, b, a}。

最初mergesort(a, b, low, pivot)只从低点到pivot(包括pivot)排序，而mergesort(a, b, pivot+1, high) 从枢轴（不包括枢轴）到高点排序。

在我提供的情况下，这意味着第一次调用合并排序时，主元将是 c。这意味着 {e,b,c} 将全部按第一次合并排序排序，而 {b, a} 将按第二次合并排序排序。

有关详细信息，请参阅此 answer

Answer 2

跟进 Rohlex32 的回答（正确答案应归功于他的回答）。

my question is why mergesort(a,b,pivot+1,high) is called?

正如Rohlex32的回答，这是因为mergesort(a, b, low, high)，使用high作为最后一个要排序的索引，所以mergesort(a, b, low, pivot), 包括元素在[枢轴].

合并排序的替代实现使用开始和结束索引，其中结束索引比最后一个索引大 1。对 mergesort 的初始调用是

mergesort(a, b, 0, sizeof(a)/sizeof(a[0]));

这样的合并排序函数与上面的有点不同：

void mergesort(int *a, int *b, int begin, int end)
{
    int mid = (begin+end)/2;
    if((end - begin) < 2)
        return;
    mergesort(a, b, begin, mid);    // sort from begin to mid-1
    mergesort(a, b, mid, end);      // sort from mid   to end-1
    merge(a, b, begin, mid, end);   // merge the two parts
}

归并排序算法的调用机制

mechanism of calling of merge sort algorithm

sorting

algorithm

recursion

mergesort

例如。