2.归并排序的优化

主要介绍两个地方的优化：

// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort2(T arr[], int l, int r){

    //优化1：
    // 对于小规模数组,使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }

    int mid = (l+r)/2;
    __mergeSort2(arr, l, mid);
    __mergeSort2(arr, mid+1, r);
    // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
    // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
    //优化2:
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}

对于优化1来讲，对于近乎所有的高级排序算法 都存在一种优化就是递归到底的情况，当我们递归到数据元素非常少时转而使用插入排序，数据比较少时，数组近乎有序的概率就比较大。

对于优化2来讲，是对于非常有序的数组才有效，但是对于一般情况，有一定的性能损失，损失在比较操作上。