算法：混合归并排序和插入排序执行时间

美好的一天，SO社区，

我是一名计算机科学学生，目前正在进行合并排序和插入排序相结合的实验。据了解，对于一定的阈值S，InsertionSort将比MergeSort具有更快的执行时间。因此，通过合并两种排序算法，总运行时间将得到优化。

然而，在使用1000个样本量和不同大小的S进行多次实验后，实验结果并没有每次都给出明确的答案。这是获得的更好结果的图片（请注意，一半的时间结果并不那么明确）：

现在，尝试相同的算法代码，样本大小为 3500：

最后，尝试使用相同的算法代码，样本大小为 500,000（请注意，y 轴以毫秒为单位：

尽管从逻辑上讲，当 S

目前，这些是我学到的时间复杂度：

归并排序：O(n log n)

插入排序：

• 最佳情况：θ(n)
• 最坏情况：θ(n^2)

最后，我在网上找到了一个资源：https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort其中指出：

混合合并插入排序：

• 最佳情况：θ(n + n log (n/x))
• 最坏情况：θ(nx + n log (n/x))

我想问一下CS社区有没有结果显示明确的证据表明，低于某个阈值 S 时，混合归并排序算法比普通归并排序算法效果更好，如果是这样，为什么?

非常感谢社区，这可能是一个微不足道的问题，但它确实会澄清我目前关于时间复杂度等问题的许多问题:)

注意：我使用 Java 进行算法编码，运行时可能会受到 Java 在内存中存储数据的方式的影响。

Java代码：

 public static int mergeSort2(int n, int m, int s, int[] arr){
        int mid = (n+m)/2, right=0, left=0;
        if(m-n<=s)
            return insertSort(arr,n,m);
        else
        {
            right = mergeSort2(n, mid,s, arr);
            left = mergeSort2(mid+1,m,s, arr);
            return right+left+merge(n,m,s,arr);
        }      
    }

    public static int insertSort(int[] arr, int n, int m){
        int temp, comp=0;
        for(int i=n+1; i<= m; i++){
            for(int j=i; j>n; j--){ 
                comp++;
                comparison2++;
                if(arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
                else
                    break;
            }
        }
        return comp;
    }

    public static void shiftArr(int start, int m, int[] arr){
        for(int i=m; i>start; i--)
            arr[i] = arr[i-1];     
    }

public static int merge(int n, int m, int s, int[] arr){
        int comp=0;
        if(m-n<=s)
            return 0;
        int mid = (n+m)/2;
        int temp, i=n,  j=mid+1;
        while(i<=mid && j<=m)
        {
            comp++;
            comparison2++;


            if(arr[i] >= arr[j])
            {
                if(i==mid++&&j==m && (arr[i]==arr[j]))
                    break;
                temp = arr[j];
                shiftArr(i,j++,arr);
                arr[i] = temp;
                if(arr[i+1]==arr[i]){
                   i++;
                }
            }
            i++;


        }
        return comp;
    }

示例代码不是传统的合并排序。合并函数会移动数组，而不是合并原始数组和临时工作数组之间的运行并返回。

我测试了自上而下和自下而上的合并排序，两者都需要大约 42 毫秒 == 0.042 秒来对 500,000 个 32 位整数进行排序，而图中的明显结果则慢了 1000 倍，大约需要 42 秒，而不是 42 毫秒。我还测试了 10,000,000 个整数，排序需要 1 秒多一点的时间。

过去，我使用 C++ 将自下而上合并排序与混合自下而上合并/插入排序进行比较，对于 1600 万 (2^24 == 16,777,216) 32 位整数，使用 S 的混合排序大约快 8% == 16. S == 64 比 S == 16 稍慢。 Visual Studio std::stable_sort 是自下而上合并排序（临时数组是原始数组大小的 1/2）和插入排序的变体，并使用 S == 32。

对于小型数组，插入排序比合并排序更快，这是缓存局部性和使用插入排序对小型数组进行排序所需的更少指令的结合。对于伪随机数据和 S == 16 到 64，插入排序的速度大约是合并排序的两倍。

相对增益随着阵列尺寸的增加而减小。考虑到自底向上归并排序的影响，当S == 16时，只优化了4次归并排序。在我的测试用例中，有 2^24 == 16,777,216 个元素，即 4/24 = 1/6 ~= 16.7% 的传递次数，导致大约 8% 的改进（因此插入排序的速度大约是合并的两倍对这 4 个通道进行排序）。仅合并排序的总时间约为 1.52 秒，混合排序的总时间约为 1.40 秒，比仅需要 1.52 秒的过程增加了 0.12 秒。对于自上而下的合并排序，当 S == 16 时，将优化 4 个最深的递归级别。

更新 - 时间复杂度为 O(n log(n)) 的混合就地合并排序/插入排序的 Java 代码示例。 （注意 - 由于递归，辅助存储仍然在堆栈上消耗。）就地部分是在合并步骤期间通过交换合并到的区域中的数据与合并自的区域中的数据来完成的。这不是稳定的排序（由于合并步骤期间的交换，不保留相等元素的顺序）。对 500,000 个整数进行排序大约需要 1/8 秒，因此我将其增加到 1600 万 (2^24 == 16777216) 个整数，这需要 4 秒多一点的时间。不使用插入排序时，排序耗时约 4.524 秒，使用 S == 64 的插入排序时，排序耗时约 4.150 秒，增益约 8.8%。使用基本相同的 C 代码，改进较小：从 2.88 秒缩短到 2.75 秒，大约提高了 4.5%。

package msortih;
import java.util.Random;

public class msortih {

    static final int S = 64;    // use insertion sort if size <= S

    static void swap(int[] a, int i, int j) {
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
    }

    // a[w:] = merged a[i:m]+a[j:n]
    // a[i:] = reordered a[w:]
    static void wmerge(int[] a, int i, int m, int j, int n, int w) {
        while (i < m && j < n)
            swap(a, w++, a[i] < a[j] ? i++ : j++);
        while (i < m)
            swap(a, w++, i++);
        while (j < n)
            swap(a, w++, j++);
    }  

    // a[w:]  = sorted    a[b:e]
    // a[b:e] = reordered a[w:]
    static void wsort(int[] a, int b, int e, int w) {
        int m;
        if (e - b > 1) {
            m = b + (e - b) / 2;
            imsort(a, b, m);
            imsort(a, m, e);
            wmerge(a, b, m, m, e, w);
        }
        else
            while (b < e)
                swap(a, b++, w++);
    }

    // inplace merge sort a[b:e]
    static void imsort(int[] a, int b, int e) {
        int m, n, w, x;
        int t;
        // if <= S elements, use insertion sort
        if (e - b <= S){
            for(n = b+1; n < e; n++){
               t = a[n];
               m = n-1;
                while(m >= b && a[m] > t){
                    a[m+1] = a[m];
                    m--;}
                a[m+1] = t;}
            return;
        }
        if (e - b > 1) {
            // split a[b:e]
            m = b + (e - b) / 2;
            w = b + e - m;
            // wsort -> a[w:e] = sorted    a[b:m]
            //          a[b:m] = reordered a[w:e]
            wsort(a, b, m, w);
            while (w - b > 2) {
                // split a[b:w], w = new mid point
                n = w;
                w = b + (n - b + 1) / 2;
                x = b + n - w;
                // wsort -> a[b:x] = sorted    a[w:n]
                //          a[w:n] = reordered a[b:x]
                wsort(a, w, n, b);
                // wmerge -> a[w:e] = merged    a[b:x]+a[n:e]
                //           a[b:x] = reordered a[w:n]
                wmerge(a, b, x, n, e, w);
            }
            // insert a[b:w] into a[b:e] using left shift
            for (n = w; n > b; --n) {
                t = a[n-1];
                for (m = n; m < e && a[m] < t; ++m)
                    a[m-1] = a[m];
                a[m-1] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[16*1024*1024];
        Random r = new Random(0);
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        imsort(a, 0, a.length);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}