主要介紹兩個地方的優(yōu)化：

// 遞歸使用歸并排序,對arr[l...r]的范圍進行排序
template<typename T>
void __mergeSort2(T arr[], int l, int r){

    //優(yōu)化1：
    // 對于小規(guī)模數(shù)組,使用插入排序
    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
    // 對于近乎有序的數(shù)組非常有效,但是對于一般情況,有一定的性能損失
    //優(yōu)化2:
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}

對于優(yōu)化1來講，對于近乎所有的高級排序算法 都存在一種優(yōu)化就是遞歸到底的情況，當我們遞歸到數(shù)據(jù)元素非常少時轉而使用插入排序，數(shù)據(jù)比較少時，數(shù)組近乎有序的概率就比較大。

對于優(yōu)化2來講，是對于非常有序的數(shù)組才有效，但是對于一般情況，有一定的性能損失，損失在比較操作上。