合并排序基例

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) A9，7，8

merge_sort(A,0,1) A9，7

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

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

Answer 1

当start == end时，它意味着只有一个元素可以“排序”。

由于start == end还意味着start < end将为false，因此函数跳过if主体中的所有内容。

所以merge_sort(A,0,0)什么也不做，但是将调用堆栈返回给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)返回(不做任何操作)，则调用merge_sort(A, 1, 1)，它只会返回。然后这两个子数组将与merge(A, 0, 0, 1)“合并”。

Answer 2

对merge_sort(A,0,0)的递归调用会立即返回，因为left == right ie:带有单个元素的片。

Answer 3

基大小写将返回原因start == end而不是start < end