其实我有个疑问，老师的测试案例的数组数量都是偶数的，但是如果数组里面的数量是奇数的话，不就多一个吗

Answer 1

liuyubobobo 2018-01-11 11:42:59

不影响哦，只不过此时将数组分成一奇一偶两部分，两部分分别继续按照归并排序的逻辑来。在最后，mergeSort里的l如果和r相等，即l==r的时候，mergeSort中传入的数组只有一个元素，此时一个元素的数组就是有序的，不需要进行任意操作。这就是下面代码递归终止条件里return做的事情。

// 递归使用归并排序,对arr[l...r]的范围进行排序    
template<typename T>    
void __mergeSort(T arr[], int l, int 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跟踪一个小数组，比如一个7个元素，5个元素，甚至只有3个元素的数组，在这个代码中是如何进行的。每一步程序是如何执行的，执行后数据是如何变化的。和自己理解的是否一样，如果不一样自己哪里想错了。这是在学习算法初期，非常重要的理解算法的方式哦：）

加油！

• 提问者 慕侠4287760 #1

  谢谢老师，我正在用Java试着，PS 老师讲课讲的太好了，我感觉自己学了三年编程，都感觉自己差好多