将MergeSort与插入排序相结合以使其更高效

合并会自动对元素进行排序。但是，当列表低于某个阈值时，可以使用插入排序进行排序：

static final int THRESHOLD = 10;static void mergeSort(int f[],int lb, int ub){    if (ub - lb <= THRESHOLD)        insertionSort(f, lb, ub);    else    {        int mid = (lb+ub)/2;        mergeSort(f,lb,mid);        mergeSort(f,mid,ub);        merge(f,lb,mid,ub);    }}

进行除此以外的任何 *** 作（除了稍微超出阈值）会 增加 合并排序所花费的时间。

尽管合并排序为O（n log n），插入排序为O（n
2），但是插入排序具有更好的常量，因此在非常小的数组上速度更快。这，这，这和这是我发现的一些相关问题。