数据量大概50个以下的时候，插入排序法的效率要高于归并排序。但是在很大的数据量的时候，归并排序又有很大的优势。基于这个原因以及它们各自排序的特点，在归并排序法往下拆分的时候，当每组数据量达到50左右的水平就改用插入排序法。通过大量的数据试验，效率确实提高不少。希望这对以后的开发有所启发。

#include <iostream>
using namespace std;

void Merge(int *, int, int, int);
void Merge_Sort(int *, int, int);
void Merge_Sort1(int *, int, int);
void Insertion_sort(int *, int);

int main()
{
    int a[] = {5, 7, 3, 8, 1, 4, 2};
    int len = sizeof(a)/sizeof(int);
    cout<<"Befor Sorting : "<<endl;
    for(int i = 0; i<len; i++)
        cout<<a[i]<<' ';
    cout<<endl;
    
    Merge_Sort1(a, 0, len-1);
    
    cout<<"After Sorting : "<<endl;
    for(int i = 0; i<len; i++)
        cout<<a[i]<<' ';
    cout<<endl;
    
    return 0;
}

void Merge_Sort(int *arr, int left, int right)
{
    if(left<right)
    {
        int middle = ( left + right ) / 2;
        Merge_Sort(arr, left, middle);
        Merge_Sort(arr, middle+1,right);
        Merge(arr, left, middle, right);
    }
    
}

void Merge(int *a, int left, int middle, int right)
{  
    int n1 = middle-left+1;
    int n2 = right-middle;
    int *L = new int[n1+1];
    int *R = new int[n2+1];
    int i, j, k;  
      
    for (i=0; i<n1; i++)
    {  
        L[i] = a[left+i];
    }  
    for (j=0; j<n2; j++)
    {  
        R[j] = a[middle+j+1];
    }  
    L[n1] = 10000000;
    R[n2] = 10000000;
  
    for (i=0, j=0, k=left; k<=right; k++)
    {  
        if (L[i]<=R[j])
        {
            a[k] = L[i];
            i++;
        }
        else
        {
            a[k] = R[j];
            j++;
        }  
    }
    delete []L;
    delete []R;
}

void Insertion_sort(int arr[], int len)
{
    int i, j;
    for(i = 1,j; i < len; i++)
    {
        j = i;
        int v = arr[j];
        while(j > 0 && arr[j-1] > v)
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = v;
    }
}

void Merge_Sort1(int *arr, int left, int right)
{
    if(right-left >=50)
    {
        int middle = ( left + right ) / 2;
        Merge_Sort(arr, left, middle);
        Merge_Sort(arr, middle+1,right);
        Merge(arr, left, middle, right);
    }
    else
    {
        Insertion_sort(arr+left, right-left+1);
    }
}

推荐您阅读更多有关于“排序算法，”的文章