__mergeSort这个递归函数退出的条件是if( l >= r), 想问这个条件是不是if( l ==r)就可以了，会有l > r这种情况发生吗？

Answer 1

liuyubobobo 2018-02-17 10:57:21

不会。这里只是一个“防御性”的写法（defensive programming），涵盖住l和r的所有关系的情况。在这里，这个递归退出条件的意思就是：如果l>=r，就什么都不做。虽然在现有的代码逻辑下，不会出现l>r的情况，但保不齐将来我们修改mergeSort的逻辑后，会出现这种情况，但不管怎样，l>=r的时候，什么都不做。

当然了，如果非常自信不会产生这种情况，也可以使用assert的方式做一个断言，把l>r的情况刨除出去。即：

template<typename T>    
void __mergeSort(T arr[], int l, int r){    
    
    assert( l <= r ); // 调用这个函数的时候，l永远不会大于r
    
    if( l == r )    
        return;    

    int mid = (l+r)/2;    
    __mergeSort(arr, l, mid);    
    __mergeSort(arr, mid+1, r);    
    __merge(arr, l, mid, r);    
}

这样在debug模式下，如果 l > r，在断言处会中断，可以进一步调试哪里的逻辑问题导致这个断言失败：）