java – 算法：混合MergeSort和InsertionSort执行时间

我测试了自上而下和自下而上的合并排序,并且两者都需要大约42毫秒== 0.042秒来排序500,000个32位整数,而图表中的明显结果是在大约42秒而不是42毫秒时慢1000倍.我还测试了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,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 j,int w) {
        while (i < m && j < n)
            swap(a,w++,a[i] < a[j] ? i++ : j++);
        while (i < m)
            swap(a,i++);
        while (j < n)
            swap(a,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,e);
            wmerge(a,e,w);
        }
        else
            while (b < e)
                swap(a,b++,w++);
    }

    // inplace merge sort a[b:e]
    static void imsort(int[] a,int e) {
        int m,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,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,b);
                // wmerge -> a[w:e] = merged    a[b:x]+a[n:e]
                //           a[b:x] = reordered a[w:n]
                wmerge(a,x,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,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));
    }
}