将MergeSort与插入排序相结合以使其更高效 [英] Combining MergeSort with Insertion sort to make it more efficient

问题描述

所以我有一个MergeSort算法，我想将MergeSort与插入排序结合使用以减少合并的开销，问题是如何?我想使用插入排序对细分进行排序，然后合并.

So I have a MergeSort algorithm and I want to combine MergeSort with Insertion sort to reduce the overhead of merging, the question is how? I want to sort the segments using insertion sort and then merge.

 public class mergesorttest{
    public static void main(String[]args){
        int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};
        mergeSort(d,0,d.length);
        for(int x:d) System.out.print(x+" "); 
        System.out.println(); 
    }

static void mergeSort(int f[],int lb, int ub){
    //termination reached when a segment of size 1 reached -lb+1=ub
    if(lb+1<ub){
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

static void merge (int f[],int p, int q, int r){
    //p<=q<=r
    int i =p; int j = q; 
    //use temp array to store merged sub-sequence
    int temp[] = new int[r-p]; int t = 0; 
    while(i<q && j<r){
        if(f[i]<=f[j]){
            temp[t] =f[i]; 
            i++;t++;
        }
        else{
            temp[t] = f[j];
            j++;
            t++;
        }

        //tag on remaining sequence
        while(i<q){
            temp[t] = f[i];
            i++;
            t++;

        }
        while(j<r){
            temp[t]=f[j];
            j++;
            t++;
        }
        //copy temp back to f
        i=p;t=0;
        while(t<temp.length){
            f[i]=temp[t];
            i++;
            t++;
        }
        }
}
}

---

public static void insertion_srt(int array[], int n, int b){
  for (int i = 1; i < n; i++){
  int j = i;
  int B = array[i];
  while ((j > 0) && (array[j-1] > B)){
  array[j] = array[j-1];
  j--;
  }
  array[j] = B;
  }
  }

推荐答案

合并会自动对元素进行排序.但是，当列表低于某个阈值时，可以使用插入排序进行排序:

The merging automatically takes care of sorting the elements. However, one can sort using insertion sort when the list gets below some threshold:

static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
    if (ub - lb <= THRESHOLD)
        insertionSort(f, lb, ub);
    else
    {
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

执行除此以外的任何操作(除了稍微超出阈值)会增加合并排序所花费的时间.

Doing anything other than this (except playing around with the threshold a little) will increase the time taken by merge sort.

尽管合并排序为O(n log n)，插入排序为O(n ² )，但是插入排序具有更好的常量，因此在非常小的数组上速度更快. 此，此，这是我发现的一些相关问题

Although merge sort is O(n log n) and insertion sort is O(n²), insertion sort has better constants and is thus faster on very small arrays. This, this, this and this are a few related questions I found.

这篇关于将MergeSort与插入排序相结合以使其更高效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！