algorithm - 如何找出最大的元素个数(数组大小)，让插入排序打败归并排序？

Question

来自插入排序的维基页面:

Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, where insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.

wiki 的引用有一个原因是，归并排序的小列表对于插入排序来说并不差。

我只想忽略这个原因。

我知道如果数组大小很小，插入排序 O(n^2) 有机会击败合并排序 O(n log n)。

我认为(不确定)这与 T(n) 中的常量有关

插入排序:T(n) = c1n^2 +c2n+c3

合并排序:T(n) = n log n + cn

现在我的问题是，在同一台机器上，同样的情况(更坏的情况)，如何找出最大的元素数，让插入排序打败归并排序？

Answer 1

很简单:

对一组样本数组进行排序，并迭代一个值 k，其中 k 是从合并切换到插入的截止点。

然后去

for(int k = 1; k < MAX_TEST_VALUE; k++) {
    System.out.println("Results for k = " + k);
    for(int[] array : arraysToTest) {
        long then = System.currentTimeMillis();
        mergeSort(array,k); // pass in k to your merge sort so it uses that
        long now = System.currentTimeMillis();
        System.out.println(now - then);
    }
}

就其值(value)而言，java.util.Arrays 类在其内部文档中对此事进行了说明:

/**
 * Tuning parameter: list size at or below which insertion sort will be
 * used in preference to mergesort or quicksort.
 */
private static final int INSERTIONSORT_THRESHOLD = 7;

/**
 * Src is the source array that starts at index 0
 * Dest is the (possibly larger) array destination with a possible offset
 * low is the index in dest to start sorting
 * high is the end index in dest to end sorting
 * off is the offset to generate corresponding low, high in src
 */
private static void mergeSort(Object[] src,
              Object[] dest,
              int low,
              int high,
              int off) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low &&
         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

在其原始序列中，它也使用 7，尽管它不使用常量值。