java - 算法 : Hybrid MergeSort and InsertionSort Execution Time

Question

美好的一天 SO 社区，

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

但是，在多次运行实验后，使用1000的样本大小，不同大小的S，每次实验的结果都没有给出确定的答案。这是获得的更好结果的图片(请注意，有一半的时间结果不是确定的):

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

最后，以500,000的样本量尝试相同的算法代码(注意y轴以毫秒为单位:

尽管从逻辑上讲，当 S<=10 时，Hybrid MergeSort 会更快，因为 InsertionSort 没有递归开销时间。然而，我的迷你实验的结果却不是这样。

目前，这些是教给我的时间复杂度:

合并排序:O(n log n)

插入排序:

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

最后，我找到了在线资源:https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort声明:

混合合并插入排序:

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

我想问一下 CS 社区中是否有结果显示明确的证据表明混合合并排序算法在低于特定阈值 S 时将比普通合并排序算法工作得更好，如果是这样，为什么 ?

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

注意:我使用 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;
    }

Answer 1

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

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

过去，使用 C++，我将自底向上归并排序与混合自底向上归并/插入排序进行比较，对于 1600 万 (2^24 == 16,777,216) 个 32 位整数，混合排序大约为 8%使用 S == 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));
    }
}