合并排序基本案例

Question

我正在练习排序算法，但我被困在这个愚蠢的问题上。

我特别不明白如何将数组划分为仅包含单个（已排序）元素的数组。我画了一个调用堆栈的例子来说明我的困惑。

void merge_sort(int A[], int start, int end) {
    if (start < end) {
        int mid = (start + end ) / 2;
        merge_sort(A, start, mid);                 
        merge_sort(A, mid + 1, end);
        merge(A, start, mid, end);   
    }                    
}

调用堆栈应如下所示

merge_sort(A,0,5) A [9,7,8,3,2,1]

merge_sort(A,0,2) A [9,7,8]

merge_sort(A,0,1) A [9,7]

merge_sort(A,0,0) -> 这里基本情况会失败，不是吗？

在这种情况下，数组不会被分割成单例数组。

Answer 1

立即递归调用merge_sort(A,0,0) returns 因为left == right 即：一个只有一个元素的切片。

Answer 2

基本情况 return 会导致开始 == 结束而不是开始 < 结束

Answer 3

当start == end时，表示只有一个元素需要“排序”。

并且由于 start == end 也意味着 start < end 将为假，因此函数将跳过 if 主体内的所有内容。

所以 merge_sort(A,0,0) 什么都不做，但是 return 将 call-stack 备份到 merge_sort(A,0,1) 。

具体查看 merge_sort(A, 0, 1) 调用，它看起来像这样：

merge_sort(A, 0, 1)
    merge_sort(A, 0, 0)  // Does nothing
    merge_sort(A, 1, 1)  // Does nothing
    merge(A, 0, 0, 1)    // Merge the two partition 0-0 with 1-1

所以一旦 merge_sort(A, 0, 0) returns（什么都不做）然后 merge_sort(A, 1, 1) 被调用，它再次只做 return。然后将两个 sub-arrays 与 merge(A, 0, 0, 1).

“合并”

合并排序基本案例

Merge Sort Base Case

c++

sorting

mergesort