c# - 为什么在 MergeSort 中使用 InsertionSort 而不是 Merge 平均速度更快？

Question

最近，我着迷于 ShellSort 算法思想，简单地在小子列表中使用 InsertionSort，然后最后对整个列表使用 InsertionSort。

所以，我想为什么不将 MergeSort 与 InsertionSort 结合使用(而不是使用 Merge() 函数，而是使用 InsertionSort)。由于 InsertionSort 擅长对部分排序的列表进行排序，而 MergeSort 的思想是将两个排序的列表合并为一个排序的列表。

然后，我测试了使用 merge() 函数的 MergeSort 和仅使用 InsertionSort() 的 MergeSort，其中包含 10,000,000 个具有随机值的元素的数组。事实证明，使用 InsertionSort() 的 MergeSort 执行速度比使用 merge() 函数的 MergeSort 快几倍。由于想出准确的数学证明超出了我的能力，所以我来这里是为了寻求逻辑上的原因。以下是我要确认的内容:

• 对于更大的数组，使用 merge() 函数的 MergeSort 的平均性能是否会优于使用 InsertionSort() 的 MergeSort，反之亦然？
• 也许我的 MergeSort with merge() 函数效率低下。
• 在 MergeSort 中使用 ShellSort 而不是 InsertionSort 会产生更快的性能吗？
• 既然 MergeSort 和 InsertionSort 不是一个坏主意，我相信已经有人发现了它。我想知道它是否有任何独特的算法名称。

---

下面是MergeSort()的实现

public static void MergeSort(int[] array)
{
    int[] aux = new int[array.Length];
    MergeSort(array, aux, 0, array.Length - 1);
}

public static void MergeSort(int[] array, int[] aux, int low, int high) 
{
    if (low >= high) return;

    int mid = (low + high) / 2;

    MergeSort(array, aux, low, mid);
    MergeSort(array, aux, mid + 1, high);

    Merge(array, aux, low, mid, high);
}

protected static void Merge(int[] array, int[] aux, int low, int mid, int high) {
    // copy into aux array
    for (int i = low; i <= high; i++) aux[i] = array[i];

    // merge
    int j = low, k = mid + 1;
    for (int o = low; o <= high; o++) {
        if (j > mid)
            array[o] = aux[k++];
        else if (k > high)
            array[o] = aux[j++];
        else if (aux[k] < aux[j])
            array[o] = aux[k++];
        else
            array[o] = aux[j++];
    }
}

下面是MergeSort with InsertionSort()

public static void MergeInsertionSort(int[] array) 
{
    MergeInsertionSort(array, 0, array.Length - 1);
}

public static void MergeInsertionSort(int[] array, int low, int high) 
{
    if (low >= high) return;
    if (low + 1 == high) {
        // sort two elements
        if (array[low] > array[high]) {
            int tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
    } else {
        int mid = (low + high) / 2;

        MergeInsertionSort(array, low, mid);
        MergeInsertionSort(array, mid + 1, high);

        // do insertion sort
        for (int i = mid + 1, j; i <= high; i++) {
            int ins = array[low];

            // move the element into correct position
            for (j = i - 1; (j >= low) && (ins < array[j]); j--) {
                array[j + 1] = array[j];
            }

            array[j + 1] = ins;
        }
    }
}

---

以下为可运行代码，您可以在您的电脑上进行测试: http://pastebin.com/4nh7L3H9

Answer 1

您根本不是在测试同一件事。您的 Merge 方法使用辅助数组，它所做的第一件事是在执行实际合并工作之前将初始数组复制到辅助数组。因此，每次调用 Merge 时，您最终都会做两倍的工作。

您可以通过对 array 和 aux 进行一些智能交换来消除该额外副本。这在非递归实现中更容易处理，但在递归版本中是可能的。我会把它留作练习。

您的 MergeInsertionSort 方法的运行方式大不相同。它根本没有进行合并。它只是拆分数组并在越来越大的范围内进行插入排序。

思路是使用插入排序，以便在范围较小时减少merge的开销。通常它看起来像这样:

public static void MergeSort(int[] array, int[] aux, int low, int high) 
{
    if (low >= high) return;

    if ((high - low) < MergeThreshold)
    {
        // do insertion sort of the range here
    }
    else
    {
        int mid = (low + high) / 2;

        MergeSort(array, aux, low, mid);
        MergeSort(array, aux, mid + 1, high);

        Merge(array, aux, low, mid, high);
    }
}

然后将 MergeThreshold 设置为您确定合适的“小范围”值。通常它在 5 到 20 的范围内，但您可能想要尝试不同的值和不同的类型(整数、字符串、复杂对象等)以获得一个好的综合数字。