如何找出最大的元素数(数组大小)，让插入排序胜过合并排序？

Question

从插入排序的wiki页面：

一些分治算法，如快速排序和合并排序，递归地将列表划分为较小的子列表，然后排序。在实践中，这些算法的一个有用的优化是使用插入排序来排序小的子列表，其中插入排序优于这些更复杂的算法。插入排序具有优势的列表的大小因环境和实现的不同而不同，但通常在8-20个元素之间。

wiki的引用有一个原因，那就是合并排序中的小列表并不是插入排序的更糟糕的情况。

我只想忽略这个原因。

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

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

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

合并排序: T(n) =n log + 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);
    }
}

值得注意的是，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，尽管它不使用常量值。

Answer 2

对于任何大小的已排序(或几乎已排序)列表，插入排序通常优于合并排序。

所以问题“如何找出最大的元素数(数组大小)，让插入排序胜过合并排序？”并不是真的正确。

编辑:只是为了让我的支持者失望:这个问题可以改写为：

1. “如何确定平均插入排序超过合并排序的最大数组大小”。这通常是通过生成小尺寸数组的样本并在这两种算法上运行实现来进行的。
2. 在他的回答中做到了这一点。
3. “在最坏情况下插入排序的最大数组大小比合并排序更好”--这可以通过简单的计算来近似回答，因为在最坏的情况下，n*(n-1)元素移动(即插入)，而mergesort总是从一个数组复制到另一个数组。由于这是一个相对较小的数目，因此考虑它是没有意义的。

Answer 3

通常，这是通过测试不同大小的数组来完成的。当n == 10时，插入排序几乎肯定会更快。当n == 100的时候，可能不会。测试，直到你的结果趋于一致。

我认为严格地通过分析来确定数字是可能的，但要做到这一点，您必须准确地知道编译器生成了什么代码，包括指令时间，并考虑到诸如缓存缺失的成本等问题。所有考虑到的事情，最简单的方法是根据经验推导它。