目录

1递归（自顶向下）

1.1版本1：

1.2 版本2：

1.3 版本3：

2.自底向上方法

2.1版本1

---

1递归（自顶向下）

1.1版本1：

void __merge(int arr[],int left,int mid,int right)
{
    int helper[right-left+1];
    for(int i=left;i<=right;i++)
    {
        helper[i-left]=arr[i];
    }
    int i=left;
    int j=mid+1;
    int k;
    for(k=left;k<=right;k++)
    {
        if(i>mid) //左半部分元素已经处理完毕
        {
            arr[k]=helper[j-left];
            j++;
        }
        else if(j>right) //右半部分已经处理完毕
        {
            arr[k]=helper[i-left];
            i++;
        }
        else if(helper[i-left]<helper[j-left])
        {
            arr[k]=helper[i-left];
            i++;
        }
        else
        {
            arr[k]=helper[j-left];
            j++;
        }

    }
    return;
}

//递归使用归并排序，对arr[l...r]的范围进行排序
void __mergeSort(int arr[],int left,int right)
{
    if(left>=right)
        return;
    int mid=left+(right-left)/2;
    __mergeSort(arr,left,mid);
    __mergeSort(arr,mid+1,right);
    __merge(arr,left,mid,right);
}

void mergeSort(int arr[],int n)
{
    __mergeSort(arr,0,n-1);
}

1.2 版本2：

版本1对近乎有序的数据排序效率较差，因为它不管左右两部分的大小怎么样，都要进行merge，但是实际上，如果arr[mid]已经小于等于arr[mid+1]的话，此时两部分合在一起也是有序的，不用进行merge。

只需要对__mergeSort函数修改如下：

//递归使用归并排序，对arr[l...r]的范围进行排序
void __mergeSort(int arr[],int left,int right)
{
    if(left>=right)
        return;
    int mid=left+(right-left)/2;
    __mergeSort(arr,left,mid);
    __mergeSort(arr,mid+1,right);
    if(arr[mid]>arr[mid+1])  //只有此时才需要进行merge
        __merge(arr,left,mid,right);
}

1.3 版本3：

版本1中，__mergeSort函数递归到只有一个数据的时候才返回，但是实际上，当数据量比较小的时候可以转而使用插入排序进而提高性能。

因为，一方面，当数据量比较小的时候，数组近乎有序的概率比较大，此时插入排序比较有优势；

另一方面，当数据量小到一定程度的时候，插入排序会比归并排序快一些。

只需要对__mergeSort函数修改如下：

//根据前面学过的插入排序进行简单的修改
void insertionSort(int arr[],int left,int right)
{
    
    for(int i=left+1;i<=right;i++)
    {
        int temp=arr[i];
        int j;
        for(j=i;j>left && arr[j-1]>temp;j--)
        {
            arr[j]=arr[j-1];
        }
        arr[j]=temp;
    }
    return;
}


//递归使用归并排序，对arr[l...r]的范围进行排序
void __mergeSort(int arr[],int left,int right)
{
    if(right-left<=15)  //15是一个经验数值，可以根据情况进行修改
    {
        insertionSort(arr,left,right);
        return;
    }
        
    int mid=left+(right-left)/2;
    __mergeSort(arr,left,mid);
    __mergeSort(arr,mid+1,right);
    if(arr[mid]>arr[mid+1])  //只有此时才需要进行merge
        __merge(arr,left,mid,right);
}

2.自底向上方法

2.1版本1

void mergeSortBU(int arr[],int n)
{
    for(int sz=1;sz<=n;sz+=sz)
    {
        for(int i=0;i+sz<n ;i+=2*sz)
        {
            __merge(arr,i,i+sz-1,min(n-1,i+2*sz-1)); //和前面的版本1相同
        }
    }
    return;
}